Interview Questions

Insert an interval into a list of sorted disjoint intervals
This is a common interview question where the input is a sorted list of disjoint intervals, and your goal is to insert a new interval and merge all necessary intervals returning a final new list. For example, if the interval list is [[1,5], [10,15], [20,25]] and you need to insert the interval [12,27], then your program should return the new list: [[1,5], [10,27]].

## Algorithm

(1) Create an array where the final intervals will be stored. (2) Push all the intervals into this array that come before the new interval you are adding. (3) Once we reach an interval in that comes after the new interval, add our new interval to the final array. (4) From this point, check each remaining element in the array and determine if the intervals need to be merged.

## Example

intervals = [[1,5], [10,15], [20,25]] insert = [12,27] final = [] Begin looping through the array: 1st interval = [1,5] This interval comes before [12,27] so just add it to final. final = [[1,5]] 2nd interval = [10,15] This interval overlaps with our interval, [12,27], because 12 is between 10 and 15. So add the new interval to final. final = [[1,5], [12,27]] Now we check each remaining interval in the array and determine if we can merge somehow. 2nd interval = [10,15] This interval overlaps with the last element in final, so merge by taking the minimum start interval and maximum end interval. Minimum of (10, 12) and maximum of (15, 27) gives us: [10,27]. Now replace the last interval in final with this merged interval. final = [[1,5], [10,27]] 3rd interval = [20,25] This interval overlaps with the last element in final, so merge by taking the minimum start interval and maximum end interval. Minimum of (10, 20) and maximum of (27, 25) gives us: [10,27]. Now replace the last interval in final with this merged interval. final = [[1,5], [10,27]] No more intervals in the original array, so: final = [[1,5], [10,27]].

## Code

```function insertInterval(arr, interval) {

var newSet = [];
var endSet = [];
var i = 0;

// add intervals that come before the new interval
while (i < arr.length && arr[i][1] < interval[0]) {
newSet.push(arr[i]);
i++;
}

// add our new interval to this final list
newSet.push(interval);

// check each interval that comes after the new interval to determine if we can merge
// if no merges are required then populate a list of the remaining intervals
while (i < arr.length) {
var last = newSet[newSet.length - 1];
if (arr[i][0] < last[1]) {
var newInterval = [Math.min.apply(null, [last[0], arr[i][0]]), Math.max.apply(null, [last[1], arr[i][1]])];
newSet[newSet.length - 1] = newInterval;
} else {
endSet.push(arr[i]);
}
i++;
}

return newSet.concat(endSet);

}

insertInterval([[1,5],[10,15],[20,25]], [12,27]);
//insertInterval([[6,7]], [1,9]);
//insertInterval([[6,7]], [1,5]);
//insertInterval([[1,5]], [6,7]);
//insertInterval([[1,5],[6,11],[13,20],[40,50]], [12,19]);
//insertInterval([[1,5],[10,15],[20,25]], [2,6]);
//insertInterval([[1,5],[6,11],[13,20],[25,30],[32,55]], [12,45]);
//insertInterval([[1,5],[6,11],[20,22]], [24,45]);
```
```def insertInterval(arr, interval):

newSet = []
endSet = []
i = 0

# add intervals that come before the new interval
while i < len(arr) and arr[i][1] < interval[0]:
newSet.append(arr[i])
i += 1

# add our new interval to this final list
newSet.append(interval)

# check each interval that comes after the new interval to determine if we can merge
# if no merges are required then populate a list of the remaining intervals
while i < len(arr):
last = newSet[-1]
if arr[i][0] < last[1]:
newInterval = [min([last[0], arr[i][0]]), max([last[1], arr[i][1]])]
newSet[-1] = newInterval
else:
endSet.append(arr[i])
i += 1

return newSet + endSet

print insertInterval([[1,5],[10,15],[20,25]], [12,27]);
#print insertInterval([[6,7]], [1,9]);
#print insertInterval([[6,7]], [1,5]);
#print insertInterval([[1,5]], [6,7]);
#print insertInterval([[1,5],[6,11],[13,20],[40,50]], [12,19]);
#print insertInterval([[1,5],[10,15],[20,25]], [2,6]);
#print insertInterval([[1,5],[6,11],[13,20],[25,30],[32,55]], [12,45]);
#print insertInterval([[1,5],[6,11],[20,22]], [24,45]);
```

## Running time

This algorithm runs in O(n) time because, in the worst case, we need to insert the new interval to the beginning of the array and then compare and merge every single other interval in the array, but this would still require only one pass through the array.

## Sources

mrdaniel published this on 11/24/15 |
• +
• 0
• -
• Why does the code have a separate array for the endset? Instead of pushing to the endset, can't you just push to the newset and the return the newset?
• +
• 0
• -
• ```def insertInterval(arr, interval): newset=[] go=True for v in arr: if go: if v[0] <= interval[0] <=v[1] or interval[0] <=v[0]: newset.append([min(v[0],interval[0]),max(v[1],interval[1])]) go=False else: newset.append(v) else: newset=insertInterval(newset,v) if go: newset.append(interval) return newset print(insertInterval([[1,5],[10,15],[20,25]], [2,6]))```
• +
• 0
• -
• Here's my solution,This version is a little nicer for languages where it is expensive to make copies of lists, and instead modifies the single existing list.
```import unittest

def myInsertInterval(arr, interval):
i = 0
# search for insertion point
while i < len(arr) and interval[0] > arr[i][0]:
i += 1

# insert our new interval
arr.insert(i, interval) #i now points to the inserted interval

# check each interval that comes after the new interval to determine if we can merge
while i < len(arr):
#if arr[i].end >= next.start
if i and arr[i-1][1] >= arr[i][0]:
arr[i-1][0] = min([arr[i-1][0], arr[i][0]]) #update with smallest start
arr[i-1][1] = max([arr[i-1][1], arr[i][1]]) #update with largest end
arr.pop(i)  #remove node to the right
else:
i = i+1

return arr

class TestInsertInterval(unittest.TestCase):
def test_insertEmptyToEmptyList(self):
self.assertEqual(myInsertInterval([], []), [[]], "Expected [[]]")
def test_insertToEmptyList(self):
self.assertEqual(myInsertInterval([], [1, 2]), [[1, 2]], "Expected [[1, 2]]")
def test_insertSimpleAtEnd(self):
self.assertEqual(myInsertInterval([[1, 2]], [3, 4]), [[1, 2], [3, 4]], "Expected [[1, 2], [3, 4]]")
def test_insertSimpleAtBeginning(self):
self.assertEqual(myInsertInterval([[3, 4]], [1, 2]), [[1, 2], [3, 4]], "Expected [[1, 3], [6, 7]]")
def test_insertAndMergeAtBeginning(self):
self.assertEqual(myInsertInterval([[6, 7]], [1, 6]), [[1, 7]], "Expected [[1, 7]]")
def test_insertAndMergeAtEnd(self):
self.assertEqual(myInsertInterval([[0, 6]], [6, 7]), [[0, 7]] , "Expected [[0, 7]]")
def test_insertOverlappingBothSidesOfExisting(self):
self.assertEqual(myInsertInterval([[6, 7]], [1, 9]), [[1, 9]] , "Expected [[1, 9]]")
def test_insertWithinExistingInterval(self):
self.assertEqual(myInsertInterval([[1, 9]], [6, 7]), [[1, 9]] , "Expected [[1, 9]]")
def test_insertAndMergeBeginningExact(self):
self.assertEqual(myInsertInterval([[6, 7]], [1, 6]), [[1, 7]], "Expected [[1, 7]]")
def test_insertAndMerge2Intervals(self):
self.assertEqual(myInsertInterval([[1, 5], [10, 15], [20, 25]], [12, 22]), [[1, 5], [10, 25]], "Expected [[1, 5], [10, 25]]")
def test_insertAndMerge3Intervals(self):
self.assertEqual(myInsertInterval([[1, 2], [10, 11], [20, 21]], [2, 30]), [[1, 30]], "Expected [[1,30]]")
def test_insertExisting(self):
self.assertEqual(myInsertInterval([[1, 2], [3, 4]], [1, 2]), [[1, 2], [3, 4]], "Expected [[1, 2], [3, 4]]")

if __name__ == '__main__':
unittest.main()

```