Java solution with explanation

  • 0
    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>() {
            public int compare(Interval o1, Interval o2) {
                return, o2.start);
        // No matter what the first interval must be in the result list.
        List<Interval> result = new ArrayList<Interval>();
        // 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.                
            } 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.
        return result;

Log in to reply

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