// MARK: - 56. Merge Intervals

// Есть список интервалов, нужно объединить интервалы которые возможно объединить
// Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
// Output: [[1,6],[8,10],[15,18]]

// Решение
// Нужно отсортировать интервалы по возрастанию первого числа
// Потом пройтись по каждому и смотреть меньше ли (начало текущего) (конца предидущего) и объединять или нет
// Нужно отдельно обработать ситуацию когда один интервал входит в другой: [1, 4], [ 2, 3]

func merge(_ intervals: [[Int]]) -> [[Int]] {
    let sorted = intervals.sorted {$0[0] < $1[0]}
    var result = [[Int]]()

    var prevInterval = sorted[0]

    for interval in sorted {

        if interval[0] <= prevInterval[1] {
            // проверяем ситуацию когда один интервал входит в другой
            let maxEnd = max(prevInterval[1], interval[1])
            prevInterval = [prevInterval[0], maxEnd]
        } else {
            result.append(prevInterval)
            prevInterval = interval
        }
    }
    // Обрабатываем последний элемент
    result.append(prevInterval)
    return result
}

var intervals = [[15,18],[2,6],[1,3],[8,10]]
merge(intervals)