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].
One pass merge as go solution
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
| * 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> insert(List<Interval> intervals, Interval newInterval) { if (intervals == null || intervals.size() < 1) return Arrays.asList(newInterval); int index = 0; while (index < intervals.size() && intervals.get(index).end < newInterval.start) index++; while (index < intervals.size() && intervals.get(index).start <= newInterval.end){ newInterval = new Interval( Math.min(intervals.get(index).start, newInterval.start), Math.max(intervals.get(index).end, newInterval.end) ); intervals.remove(index); } intervals.add(index, newInterval); return intervals; } }
|
my insert first then merge solution
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 41 42 43 44 45
| * 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> insert(List<Interval> intervals, Interval newInterval) { if (intervals == null || intervals.size() == 0) return Arrays.asList(newInterval); int start = -1, end = intervals.size(), middle = (start + end) / 2; while (start < end) { if (start == middle || end == middle) break; Interval middleInterval = intervals.get(middle); if (middleInterval.start < newInterval.start) { start = middle; } else { end = middle; } middle = (start + end) / 2; } if (start == middle) { intervals.add(start + 1, newInterval); } else { end = end - 1 < 0 ? 0 : end - 1; intervals.add(end, newInterval); } List<Interval> result = new LinkedList<Interval>(); Interval prev = null; for (Interval interval : intervals) { if (prev == null || prev.end < interval.start) { result.add(interval); prev = interval; } else { prev.end = Math.max(prev.end, interval.end); } } return result; } }
|