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].
思路：分情况看：首先假设对于new,end < cur.start，那么就非常easy的知道应该插入cur的前面：相反，此时假设new.start > cur.end的话。那么就能继续往下走了。否则就是这种情况：此时两个区间是有重叠的。各自取左右边界的最小和最大值。
package code;import java.util.ArrayList;import java.util.List;import java.util.ListIterator;public class Insert_Interval { public static void main(String[] args) { List intervals = new ArrayList (); Insert_Interval root = new Insert_Interval(); Insert_Interval.Interval s1 = root.new Interval(1, 3); intervals.add(s1); intervals.add(new Insert_Interval().new Interval(6, 9)); Insert_Interval.Interval t = root.new Interval(2, 5); Insert_Interval.Solution solution = root.new Solution(); List ans = solution.insert(intervals, t); for (Interval interval : ans) { System.out.println(interval.start + "-" + interval.end); } } 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 insert(List intervals, Interval newInterval) { if (intervals == null || newInterval == null) return intervals; if (intervals.size() == 0) intervals.add(newInterval); ListIterator it = intervals.listIterator(); while (it.hasNext()) { Interval tmp = it.next(); if (newInterval.end < tmp.start) { it.previous(); it.add(newInterval); return intervals; } else { if (newInterval.start > tmp.end) continue; else { newInterval.start = Math.min(tmp.start, newInterval.start); newInterval.end = Math.max(tmp.end, newInterval.end); it.remove(); } } } intervals.add(newInterval); return intervals; } }} 版权声明：本文博客原创文章，博客，未经同意，不得转载。
