# 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]`

.

# Notes:

- The original list is valid, so we can take advantage of that, when traversing the list, if the new interval overlap with any in the original list, remove the one in the list, and update the new interval to the merge of those two.
- Use iterator to operate (add/remove) on the list at the same time of traversing. Note that when doing add(), should go to previous first, because when get to know the location of add, in fact we need add in front of current.
- To make the code concise and easy to read : For the condition to find overlapping can be very messy to list 4 overlapping ways, instead find those no-overlapping case first, and all overlapping case will be in else, then the merge can be done using Math.min/max instead of consider each case individually.

# Java Solution

/** * 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.size()==0 ){ intervals.add(newInterval); return intervals; } ListIterator<Interval> iterator = intervals.listIterator(); boolean added = false; while(iterator.hasNext()){ Interval iter= iterator.next(); if(iter.end < newInterval.start){ continue; } else if (iter.start > newInterval.end){ iterator.previous(); iterator.add(newInterval); return intervals; } else{ newInterval.start = Math.min(newInterval.start, iter.start); newInterval.end = Math.max(newInterval.end, iter.end); iterator.remove(); } } intervals.add(newInterval); return intervals; } }

Advertisements