首页 > 代码库 > [LeetCode#57]Insert Interval
[LeetCode#57]Insert Interval
The problem:
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
My first solution:
The logic behind this solution is complex and errors prone! It‘s because I have not totally understand the rational behind this problem.
public class Solution { public List<Interval> insert(List<Interval> intervals, Interval newInterval) { ArrayList<Interval> ret = new ArrayList<Interval> (); if (intervals == null) { //return ret.add(newInterval); ret.add(newInterval); return ret; } if (newInterval == null) return intervals; Interval pre = new Interval(newInterval.start, newInterval.end); boolean flag = false; //indicate if the new Interval has already been added for (int i = 0; i < intervals.size(); i++) { Interval cur = intervals.get(i); if ((cur.start>=pre.start&&cur.start<=pre.end)||(cur.end>=pre.start&&cur.end<=pre.end)||(cur.end>=pre.end&&pre.start>=cur.start)) {//overlapping happens pre.start = pre.start < cur.start ? pre.start : cur.start; pre.end = pre.end > cur.end ? pre.end : cur.end; } else { if (pre.end < cur.start && flag != true) { //the pre interval‘s range is over! ret.add(pre); flag = true; //casue I put off the add of the answer at next independent interval } ret.add(cur); } } if (flag != true)//in the case of the last interval! ret.add(pre); return ret; }}
A more elegant way!!!
A advanced analysis
The idea behind this solution is simple and great, you must master related skills.The key idea: [ ... ][ ][ ][ ][ ][ ][]we should able to figure out the first and last overlapping intervals with newInterval.1. how to find out the first? At the first collision interval, as shown above, the start boundary must less than the end boundary of the first.We use the contradiction as loop condition: before the first collision, the intervals end boundary must ahead of the newInterval‘s start boundary. Use this property, we could reach the first collision window. note the loop condition.int i = 0;while(i<intervals.size() && (newInterval.start>intervals.get(i).end)) { //only when not collision, we move on. ret.add(intervals.get(i)); i++;}2. As the same, once we dectect the first collision, begin from the interval, all collision interval‘s start boundary must lessthan the newInterval‘s start boundary. while (i<intervals.size() && (newInterval.end>=intervals.get(i).start)) { newInterval.end = newInterval.end > intervals.get(i).end ? newInterval.end : intervals.get(i).end; i++;}Since we detect the first overlapping interval, until we reach the last interval, we keep on merge newInterval through following ways: ...if (i < intervals.size()) {//must not exceed the end!!! newInterval.start = newInterval.start < intervals.get(i).start ? newInterval.start : intervals.get(i).start;}while (i<intervals.size() && (newInterval.end>=intervals.get(i).start)) { newInterval.end = newInterval.end > intervals.get(i).end ? newInterval.end : intervals.get(i).end; i++;}The while loop is because that, the checking codition is "newInterval.end>=intervals.get(i).start)", when means when the interval meets the condition of collision, we merge it into the collision interval.
The solution:
public class Solution { public List<Interval> insert(List<Interval> intervals, Interval newInterval) { ArrayList<Interval> ret = new ArrayList<Interval> (); if (intervals == null || intervals.size() == 0) { ret.add(newInterval); return ret; } if (newInterval == null) return intervals; int i = 0; while(i<intervals.size() && (newInterval.start>intervals.get(i).end)) { ret.add(intervals.get(i)); i++; } if (i < intervals.size()) {//must not exceed the end!!! newInterval.start = newInterval.start < intervals.get(i).start ? newInterval.start : intervals.get(i).start; } while (i<intervals.size() && (newInterval.end>=intervals.get(i).start)) { newInterval.end = newInterval.end > intervals.get(i).end ? newInterval.end : intervals.get(i).end; i++; } ret.add(newInterval); while (i<intervals.size()) { ret.add(intervals.get(i)); i++; } return ret; }}
[LeetCode#57]Insert Interval
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。