**57. Insert Interval **

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].

### Approach: Efficient Solution

** Logic **

There are 3 cases with the new interval that to be inserted.

- New interval overlaps with the existing interval
- New interval does not overlap: it is the first interval
- New interval does not overlap: it is the last interval

- Case 1: interval overlaps:
- Start with the first overapped interval, let's call it startIntr;
- find all the subsequent intervals that overlap with the new interval, Let's call it

endIntr; - create insert new interval such that:
- insIntr.start = min (startIntr.start , newInterval.start);
- insIntr.end = max (endIntr.end, newIntr.end);
- insert insIntr;

- Case 2: New interval does not overlap: it is the first interval
- For this, check if newInterval.end is smaller that intervals[i] and it is not

already inserted - If the above conditions is true, insert the new interval

- For this, check if newInterval.end is smaller that intervals[i] and it is not
- Case 3: New interval does not overlap: it is the last interval
- If new interval is not get added, it must be the last interval

**C#**

```
/**
* Definition for an interval.
* public class Interval {
* public int start;
* public int end;
* public Interval() { start = 0; end = 0; }
* public Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
// returns min
private int min(int a, int b)
{
return a<b?a:b;
}
// returns max
private int max(int a, int b)
{
return a<b?b:a;
}
//
// check if interval a and b are overlapping with each other
//
private bool bOverlapped(Interval a, Interval b)
{
return !(a.end < b.start || a.start > b.end );
}
public IList<Interval> Insert(IList<Interval> intervals, Interval newInterval) {
IList intr = new List<Interval>();
bool bFlag = false;
int i = 0;
while(i < intervals.Count)
{
// Case 1: Find overlapping intervals
if(bOverlapped(newInterval, intervals[i]) == true)
{
// c is first interval which overlaps with newInterval
Interval c = intervals[i];
// find subsequent overlapping intervals
while(i<intervals.Count && bOverlapped(newInterval, intervals[i]))
i++;
// we have found the last overapped interval at i-1
c.start = min(c.start, newInterval.start);
c.end = max(newInterval.end, intervals[i-1].end);
intr.Add(c);
// mark flag as true. it indicates that interval is added
bFlag = true;
}
// Case 2: New interval does not overlap: it is the first interval
else if (newInterval.end < intervals[i].end && bFlag == false)
{
// Add new interval if it is not already added
intr.Add(newInterval);
intr.Add(intervals[i++]);
bFlag = true;
}
else
intr.Add(intervals[i++]);
}
// bFlag == false implies new interval is not added. this means 3rd Case
if (bFlag == false)
intr.Add(newInterval);
return (IList<Interval>)intr;
}
}
```

**Complexity Analysis**

- Time complexity : (n).