Example: Merge Intervals - rFronteddu/general_wiki GitHub Wiki

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

If you sort by end, it might misorder intervals that start earlier but end later, causing missed merges if the second interval doesn't overlap with the first but the third does we will not merge the first and the third.

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][];
        }
        List<int[]> l = new LinkedList<>();

        // sort by start
        Arrays.sort (intervals, (a, b) -> Integer.compare(a[0], b[0]));

        int[] candidate = intervals[0];
        l.add(candidate);
 
        for(int[] interval : intervals) {
            if(currentEnd >= interval[0]) {
                // overlap
                candidate[1] = Math.max(candidate[1], interval[1]);
            } else {
                // no overlap
                candidate = interval;
                l.add(candidate);
            }
        }
        return l.toArray (new int[l.size()][]);
    }
}
⚠️ **GitHub.com Fallback** ⚠️