Solution for https://ru.stackoverflow.com/q/723419/4065

Collection.php

<?php
class Collection
{
    /** @var  Item[] */
    protected $items;

    /**
     * Collection constructor.
     * @param Item $main
     * @param Item[] $items
     */
    public function __construct(Item $main, array $items)
    {
        Assert::allIsInstanceOf($items, Item::class);

        foreach ($items as $item) {
            Assert::greaterThanEq($item->getStart(), $main->getStart());
            Assert::lessThanEq($item->getEnd(), $main->getEnd());
        }

        array_unshift($items, $main);

        $this->items = $items;
    }

    /**
     * @return int[]
     */
    public function getPeriodDots()
    {
        $dots = [];

        foreach ($this->items as $item) {
            /** @var Item $item */
            $dots = array_filter($dots, function ($dot) use ($item) {
                $inPeriod = $item->getStart() <= $dot && $dot <= $item->getEnd();

                return !$inPeriod;
            });

            $dots[] = $item->getStart();
            $dots[] = $item->getEnd();
        }
        sort($dots);

        return $dots;
    }

    /**
     * @param int[] $dots
     * @return Item[]
     */
    public function getNewItems($dots)
    {
        $startDots = array_slice($dots, 0, -1);
        $endDots = array_slice($dots, 1);

        $newItems = [];

        foreach ($startDots as $i => $start) {
            $end = $endDots[$i];

            $type = $this->getTypeForDot($start);

            $newItems[] = new Item($start, $end, $type);
        }

        return $newItems;
    }

    /**
     * @param int $dot
     * @return int
     * @throws InvalidConfigException
     */
    public function getTypeForDot($dot)
    {
        /** @var Item[] $items */
        $items = array_reverse($this->items);

        foreach ($items as $item) {
            if ($item->getStart() <= $dot && $dot < $item->getEnd()) {
                return $item->getType();
            }
        }

        throw new InvalidConfigException('Не нашлось ни одного периода для точки');
    }

    /**
     * @param Item[] $items
     * @return Item[]
     */
    public function optimizePeriods($items)
    {
        $newItems = [];
        $item = array_shift($items);
        $start = $item->getStart();
        $end = $item->getEnd();
        $type = $item->getType();

        foreach ($items as $item) {
            if ($item->getType() === $type) {
                $end = $item->getEnd();
                continue;
            }

            $newItems[] = new Item($start, $end, $type);

            $start = $item->getStart();
            $end = $item->getEnd();
            $type = $item->getType();
        }

        $newItems[] = new Item($start, $end, $type);

        return $newItems;
    }

    public function getOptimized()
    {
        $dots = $this->getPeriodDots();
        $items = $this->getNewItems($dots);
        return $this->optimizePeriods($items);
    }
}

CollectionTest.php

<?php
class CollectionTest extends \Codeception\Test\Unit
{
    /**
     * @var \tests\UnitTester
     */
    protected $tester;

    public function getPeriodDotsProvider()
    {
        return [
            [
                new Item(0, 10, 'busy'),
                [
                    new Item(1, 9, 'free'),
                    new Item(2, 6, 'busy'),
                    new Item(5, 8, 'busy'),
                ],
                [0, 1, 2, 5, 8, 9, 10],
            ],
            [
                new Item(0, 10, 'busy'),
                [
                    new Item(1, 9, 'free'),
                    new Item(2, 6, 'busy'),
                    new Item(5, 8, 'busy'),
                    new Item(2, 8, 'free'),
                ],
                [0, 1, 2, 8, 9, 10],
            ],
            [
                new Item(0, 10, 'busy'),
                [
                    new Item(1, 2, 'free'),
                    new Item(3, 4, 'busy'),
                ],
                [0, 1, 2, 3, 4, 10],
            ],
        ];
    }

    /**
     * @dataProvider getPeriodDotsProvider
     * @param Item $main
     * @param Item[] $items
     * @param int[] $result
     */
    public function testGetPeriodDots($main, $items, $result)
    {
        $collection = new Collection($main, $items);

        $dots = $collection->getPeriodDots();

        $this->assertSame($result, $dots);
    }

    public function testGetNewItems()
    {
        $result = [
            [0, 1, 'busy'],
            [1, 2, 'free'],
            [2, 5, 'busy'],
            [5, 8, 'busy'],
            [8, 9, 'free'],
            [9, 10, 'busy'],
        ];

        $collection = new Collection(
            new Item(0, 10, 'busy'),
            [
                new Item(1, 9, 'free'),
                new Item(2, 6, 'busy'),
                new Item(5, 8, 'busy'),
            ]
        );

        $dots = [0, 1, 2, 5, 8, 9, 10];

        /** @var Item[] $output */
        $output = $collection->getNewItems($dots);

        $this->assertCount(6, $output);

        foreach ($output as $i => $item) {
            $this->assertSame($result[$i][0], $item->getStart());
            $this->assertSame($result[$i][1], $item->getEnd());
            $this->assertSame($result[$i][2], $item->getType());
        }
    }

    public function testOptimizePeriods()
    {
        $items = [
            new Item(1, 2, 0),
            new Item(2, 3, 0),
            new Item(3, 4, 1),
            new Item(5, 6, 1),
            new Item(6, 7, 1),
            new Item(7, 8, 0),
        ];

        $result = [
            [1, 3, 0],
            [3, 7, 1],
            [7, 8, 0],
        ];

        $collection = new Collection(new Item(0, 10, 0), $items);

        $output = $collection->optimizePeriods($items);

        $this->assertCount(count($result), $output);

        foreach ($output as $i => $item) {
            $this->assertSame($result[$i][0], $item->getStart());
            $this->assertSame($result[$i][1], $item->getEnd());
            $this->assertSame($result[$i][2], $item->getType());
        }
    }

    public function getOptimizedProvider()
    {
        return [
            'simple' => [
                [
                    new Item(3, 4, 1),
                    new Item(1, 2, 1),
                ],
                [
                    [0, 1, 0],
                    [1, 2, 1],
                    [2, 3, 0],
                    [3, 4, 1],
                    [4, 10, 0],
                ],
            ],
            'rewrite' => [
                [
                    new Item(2, 8, 1),
                    new Item(1, 9, 0),
                ],
                [
                    [0, 10, 0],
                ],
            ],
            'edges' => [
                [
                    new Item(0, 1, 1),
                    new Item(9, 10, 1),
                ],
                [
                    [0, 1, 1],
                    [1, 9, 0],
                    [9, 10, 1],
                ],
            ],
            'neighbors' => [
                [
                    new Item(0, 1, 1),
                    new Item(1, 2, 1),
                    new Item(2, 3, 1),
                    new Item(3, 4, 1),

                    new Item(5, 6, 1),
                    new Item(6, 7, 1),
                    new Item(7, 8, 1),
                ],
                [
                    [0, 4, 1],
                    [4, 5, 0],
                    [5, 8, 1],
                    [8, 10, 0],
                ],
            ],
            'multiple-types' => [
                [
                    new Item(0, 1, -1),
                    new Item(1, 2, 2),
                    new Item(2, 3, 3),
                    new Item(3, 4, 4),
                    new Item(4, 5, 5),
                    new Item(5, 6, 6),
                    new Item(6, 7, 'String'),
                    new Item(7, 8, 8.5),
                ],
                [
                    [0, 1, -1],
                    [1, 2, 2],
                    [2, 3, 3],
                    [3, 4, 4],
                    [4, 5, 5],
                    [5, 6, 6],
                    [6, 7, 'String'],
                    [7, 8, 8.5],
                    [8, 10, 0],
                ],
            ],
        ];
    }

    /**
     * @dataProvider getOptimizedProvider
     * @param Item[] $items
     * @param array $result
     */
    public function testGetOptimized(array $items, array $result)
    {
        $collection = new Collection(new Item(0, 10, 0), $items);

        $output = $collection->getOptimized();

        $this->assertCount(count($result), $output);

        foreach ($output as $i => $item) {
            $this->assertSame($result[$i][0], $item->getStart());
            $this->assertSame($result[$i][1], $item->getEnd());
            $this->assertSame($result[$i][2], $item->getType());
        }
    }
}

Item.php

<?php
class Item
{
    protected $start;
    protected $end;
    protected $type;

    /**
     * Item constructor.
     * @param int $start
     * @param int $end
     * @param int $type
     */
    public function __construct($start, $end, $type)
    {
        Assert::integer($start);
        Assert::integer($end);
        Assert::greaterThan($end, $start);

        $this->start = $start;
        $this->end = $end;
        $this->type = $type;
    }

    /**
     * @return int
     */
    public function getStart()
    {
        return $this->start;
    }

    /**
     * @return int
     */
    public function getEnd()
    {
        return $this->end;
    }

    /**
     * @return int
     */
    public function getType()
    {
        return $this->type;
    }
}