Java solution with explanation


  • 0
    L
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() == 0) {
            return new ArrayList<Interval>();
        }
        
        // Sort the list by start first.
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return Integer.compare(o1.start, o2.start);
            }
        });
        
        // No matter what the first interval must be in the result list.
        List<Interval> result = new ArrayList<Interval>();
        result.add(intervals.get(0));
        
        // Go through the rest intervals in the list.
        for (int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            Interval last = result.get(result.size() - 1);
            if (cur.end <= last.end) {
                // If current interval's end is not greater than last interval's end,
                // that mean current interval is `inside` of the last interval, so
                // We do not need to do anything.                
                continue;
            } else if (cur.start <= last.end) {
                // If there is an intersection between current and last interval,
                // then we can just update the last interval's end (like expanding).
                last.end = cur.end;
            } else {
                // If current interval is not inside the last interval, and has no
                // intersection with last interval, then we add it into the result list.
                result.add(cur);
            }
        }
        return result;
    }

Log in to reply
 

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