[LeetCode] 56. Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given
return
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):
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
Post a Comment