My easy to understand O(nlogn) Java solution, based on sort by start time, with comments.


  • 0
    C
     public List<Interval> merge(List<Interval> intervals) {
            Comparator<Interval> comparator = new Comparator<Interval>() {
                public int compare(Interval object1, Interval object2) {
                    // Sort by start time 
                    return object1.start - object2.start;
                }
            };
            
            Collections.sort(intervals, comparator);
            for (int i = 1; i < intervals.size(); i++) {
                // Compare start time of previous interval with end time of current interval
                Interval previous = intervals.get(i - 1), current = intervals.get(i);
                if (previous.end >= current.start) {
                    // Take smaller of the start times, and larger of the end times
                    current.start = previous.start; 
                    // [1 5] [2 4] => [1 5]  - Take the larger of the end times
                    current.end = previous.end > current.end ? previous.end : current.end;
                    intervals.remove(i-1);
                    i--;
                }
            }
            
            return intervals;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.