0056. Merge Intervals

https://leetcode.com/problems/merge-intervals

Description

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.

Example 1:

**Input:** intervals = [[1,3],[2,6],[8,10],[15,18]]
**Output:** [[1,6],[8,10],[15,18]]
**Explanation:** Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

**Input:** intervals = [[1,4],[4,5]]
**Output:** [[1,5]]
**Explanation:** Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

• 1 <= intervals.length <= 104

• intervals[i].length == 2

• 0 <= starti <= endi <= 104

ac

class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> res = new ArrayList<Interval>();
        // sort list
        Collections.sort(intervals, (Interval i1, Interval i2) -> {
            return i1.start - i2.start;
        });
        // dfs handle interval
        merge(intervals, 0, res);
        return res;
    }
    private void merge(List<Interval> intervals, int pos, List<Interval> res) {
        int size = intervals.size();
        if (pos >= size) return;

        int start = intervals.get(pos).start;
        int end = intervals.get(pos).end;
        for (int i = pos; i < size; i++) {
            if (i == size - 1 || intervals.get(i+1).start > end) {
                res.add(new Interval(start, end));
                merge(intervals, i+1, res);
                break;
            }
            end = Math.max(end, intervals.get(i+1).end);
        }
    }
}

ac2:

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> res = new ArrayList<Interval>();
        // edge cases
        if (intervals == null || intervals.size() <= 1) return intervals;

        // sort
        Collections.sort(intervals, (a, b) -> {return a.start - b.start;});

        // iterate list
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (Interval i : intervals) {
            if (end < i.start) {
                res.add(new Interval(start, end));
                start = i.start;
                end = i.end;
            } else {
                end = Math.max(end, i.end);
            }
        }
        // add final one
        res.add(new Interval(start, end));

        return res;
    }
}

ac3: