56. Merge Intervals

LeetCode

Intuition: if we sort intervals by the start endpoint of an interval, those merge-able intervals must be consecutive.

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        if (intervals == null || intervals.length == 0) {
            return res.toArray(new int[res.size()][]);
        }
        Arrays.sort(intervals, (i1, i2) -> {
            return i1[0] - i2[0];
        });
        for (int i = 0; i < intervals.length; i++) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            while (i + 1 < intervals.length && right >= intervals[i + 1][0]) {
                right = Math.max(right, intervals[i + 1][1]);
                i++;
            }
            res.add(new int[] {left, right});
        }
        return res.toArray(new int[res.size()][]);
    }
}