[LeetCode] Problem 56 - Merge Intervals

Posted on | In ,

Given a collection of intervals, merge all overlapping intervals.

Example

No.1

Input: [[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].

No.2

Input: [[1,4],[4,5]]

Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Code

1
2
3
4
5
6
public class Interval {
    int start;
    int end;
    Interval() { start = 0; end = 0; }
    Interval(int s, int e) { start = s; end = e; }
}
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
public List<Interval> merge(List<Interval> intervals) {
    List<Interval> result = new ArrayList<>();

    Collections.sort(intervals, new Comparator<Interval>() {
        @Override
        public int compare(Interval o1, Interval o2) {
            return o1.start - o2.start;
        }
    });

    for (Interval i : intervals) {
        if (result.size() < 1) {
            result.add(i);
            continue;
        }

        Interval last = result.get(result.size() - 1);

        if (i.start > last.end)
            result.add(i);
        else
            last.end = Math.max(last.end, i.end);
    }

    return result;
}