Merge Intervals

Leetcode #56 | Medium | Интервалы

Идея

Сортируем по началу отрезка
Заводим массив res, идем с 1 индекса по интервалам, если текущий перекрывает последний из res - обновляем последний res (начало - тоже, конец - максимум из концов), если не перекрывает - просто добавляем в res
Java hint: int[]- тоже наследник Object и валиден в качестве дженерика List<int[]>
Для конвертации res.toArray(new int[0][0])- параметр нужен для указания типа int[][], если не указать вернеться Object[]

Big-O

• Время O(Nlog(N))
• Память O(N)

Код

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> res = new ArrayList<>();
        int[] cur = intervals[0];
        res.add(cur);
        for (int[] interval : intervals) {
            if (interval[0] <= cur[1]) cur[1] = Math.max(cur[1], interval[1]);
            else { cur = interval; res.add(cur); }
        }
        return res.toArray(new int[0][0]);
    }
}