LeetCode link

Intuition

  • Sort the start in ascending order.
  • If the next start is smaller than the current end, it can be merged in. Update the end.
  • If the next start is larger, they’re separated, add the previous interval into result.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> results = new ArrayList<>();
        if (intervals.size() < 1) {
            return results;
        }
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare (Interval a, Interval b) {
                return a.start - b.start;
            }
        });
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (int i = 1; i < intervals.size(); i++) {
            Interval interval = intervals.get(i);
            if (interval.start <= end) {
                end = Math.max(end, interval.end);
            } else {
                results.add(new Interval(start, end));
                start = interval.start;
                end = interval.end;
            }
        }
        results.add(new Interval(start, end));
        return results;
    }
}