# Fast c# solution

• **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.

1. New interval overlaps with the existing interval
2. New interval does not overlap: it is the first interval
3. New interval does not overlap: it is the last interval
• Case 1: interval overlaps:
• 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
• If the above conditions is true, insert the new interval
• 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);

// 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)
{
bFlag = true;
}
else
}

// bFlag == false implies new interval is not added. this means 3rd Case
if (bFlag == false)