首页 > 代码库 > [LeetCode#56]Merge Intervals
[LeetCode#56]Merge Intervals
The problem:
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]
.
My analysis:
If you could have a clear idea about each possible conditions, when sort the interval or decide the new interval‘s start and end boundary, the problem is very easy!1. Inorder to find out ther overlapping intervals by only traversaling the List once, we need to firstly sort the intervals (according to the start of the interval). There could be two cases:1.1 Interval i2‘s start position is strictly greater than i1.1.2 Interval i2‘s start position is the same as that of the interval i1, but i2‘s end position is strictly greater than i1‘s. Note: the sort in interval is very very important, these two are classic ways. Skill: we need to write a comparator for it.Comparator<Interval> comp = new Comparator<Interval> () { @Override public int compare(Interval i1, Interval i2) { //if i1 should be ordered before i2, return negative value if (i1.start == i2.start) return i1.end - i2.end; return i1.start - i2.start; }};2. How to decide whether two intervals are overlapping?Since we scan the intervals list from the sorted order(compare start position), we only need to compare the pre window(interval)‘s end position and end window(position)‘s start position. we could classify it into two cases:Assume: Interval1 {} Interval2[]2.1 { [ } ]2.2 { [ ] }from the above analysis, we could know that we could detect overlaypping through "if (pre.end >= cur.start)", and we need to decide the new window‘s end boundary through following way:if (pre.end >= cur.start) { pre.end = (pre.end > cur.end ? pre.end : cur.end);}3. The invariant I used in this solution:3.1 iff current interval is overlapping with the pre interval, we includ the current interval into the pre interval, by adjusting the start and end position‘s value.3.2 iff not, we add the pre interval into the answer set and update the pre interval into the current one. Since we add the pre interval at the next independent interval.To use this invariant, we need: 3.1 set intervals(0) as the pre intervalInterval pre = new Interval(intervals.get(0).start, intervals.get(0).end);3.2 begin the invariant from interval(1)for (int i = 1; i < intervals.size(); i++) {...}3.3 add the last interval outside the for loop.ret.add(pre);
My solution:
public class Solution { public List<Interval> merge(List<Interval> intervals) { ArrayList<Interval> ret = new ArrayList<Interval> (); if (intervals == null || intervals.size() == 0) return ret; Comparator<Interval> comp = new Comparator<Interval> () { @Override public int compare(Interval i1, Interval i2) { if (i1.start == i2.start) return i1.end - i2.end; return i1.start - i2.start; } }; Collections.sort(intervals, comp); Interval pre = new Interval(intervals.get(0).start, intervals.get(0).end); for (int i = 1; i < intervals.size(); i++) { Interval cur = intervals.get(i); if (pre.end >= cur.start) { pre.end = (pre.end > cur.end ? pre.end : cur.end); } else { //a separtate interval ret.add(pre); pre = new Interval(cur.start, cur.end); } } ret.add(pre); return ret; }}
[LeetCode#56]Merge Intervals
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。