[LeetCode] 56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Thought process:
The idea is to sort the intervals based on their start. Then I compare the first interval's end with the next interval's start. If end is larger, we update end to be the max of the two intervals and continue to the next interval. Else, we add the overlapped interval to the result list.

Solution (Comparator):
 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
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * 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; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() == 0) {
            return intervals;
        }
        
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });
        
        List<Interval> result = new ArrayList<>();
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (Interval interval : intervals) {
            if (end >= interval.start) {
                end = Math.max(end, interval.end);
            } else {
                Interval merged = new Interval(start, end);
                result.add(merged);
                start = interval.start;
                end = interval.end;
            }
        }
        result.add(new Interval(start, end));
        
        return result;
    }
}

Solution (Lambda):
 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
28
29
30
31
32
33
34
35
/**
 * 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; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() == 0) {
            return intervals;
        }
        
        Collections.sort(intervals, (a, b) -> a.start - b.start);
        List<Interval> result = new ArrayList<>();
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        
        for (Interval interval : intervals) {
            if (end >= interval.start) {
                end = Math.max(end, interval.end);
            } else {
                Interval merged = new Interval(start, end);
                result.add(merged);
                start = interval.start;
                end = interval.end;
            }
        }
        result.add(new Interval(start, end));
        
        return result;
    }
}

Time complexity:
Say n = size of intervals. Sorting takes O(nlogn) and merging takes O(n). So the overall time complexity is O(nlogn).

Comments

Popular posts from this blog

[LeetCode] 714. Best Time to Buy and Sell Stock with Transaction Fee

[LeetCode] 269. Alien Dictionary

[LeetCode] 631. Design Excel Sum Formula