Home/

...

/

Insert Interval (medium)

Insert Interval (medium)

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Insert Interval (medium) lesson:

Press + to interact
Python 3.5
def insert(intervals, new_interval):
  merged = []
  i, start, end = 0, 0, 1
  # skip (and add to output) all intervals that come before the 'new_interval'
  while i < len(intervals) and intervals[i][end] < new_interval[start]:
    merged.append(intervals[i])
    i += 1
  # merge all intervals that overlap with 'new_interval'
  while i < len(intervals) and intervals[i][start] <= new_interval[end]:
    new_interval[start] = min(intervals[i][start], new_interval[start])
    new_interval[end] = max(intervals[i][end], new_interval[end])
    i += 1
  # insert the new_interval
  merged.append(new_interval)
  # add all the remaining intervals to the output
  while i < len(intervals):
    merged.append(intervals[i])
    i += 1
  return merged
def main():
  print("Intervals after inserting the new interval: " + str(insert([[1, 3], [5, 7], [8, 12]], [4, 6])))
  print("Intervals after inserting the new interval: " + str(insert([[1, 3], [5, 7], [8, 12]], [4, 10])))
  print("Intervals after inserting the new interval: " + str(insert([[2, 3], [5, 7]], [1, 4])))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

intervals: [[1, 3], [5, 7], [8, 12],[13,14]]
new_intervals: [8, 10]

Iteration No.

Line No.

i

merged

intervals[i][start]

intervals[i][end]

-

2-3

0

[]

-

-

1

6-7

0

[[1, 3]]

-

3

1

8

1

[[1, 3]]

-

3

2

6-7

1

[[1, 3], [5, 7]]

-

7

2

8

2

[[1, 3], [5, 7]]

-

7

1

11-13

2

[[1, 3], [5, 7]]

8

-

1

14

3

[[1, 3], [5, 7]]

8

-

-

17

3

[[1, 3], [5, 7], [8, 12]]

-

-

1

20-21

3

[[1, 3], [5, 7], [8, 12], [13, 14]]

-

-

1

22

4

[[1, 3], [5, 7], [8, 12], [13, 14]]

-

-

Sample Input #2

intervals: [[2, 3], [5, 7]]
new_interval: [1, 4]

Iteration No.

Line No.

i

merged

intervals[i][start]

intervals[i][end]

-

2-3

0

[]

-

-

1

11-13

0

[]

2

-

1

14

1

[]

2

-

-

17

1

[[1, 4]]

-

-

1

20-21

1

[[1, 4], [5, 7]]

-

-

1

22

2

[[1, 4], [5, 7]]

-

-

Step-by-step solution construction

There are three main parts of the solution:

  1. Identify the intervals before the new interval
  2. Merge the intervals that overlap the new interval
  3. Append the intervals greater than the new interval to the final intervals

In the code below, we are identifying the intervals which end before the start time of the new interval.

On lines 8-12, we add intervals[i] to the merged list if intervals[i][end] is less than new_interval[start]

Press + to interact
Python 3.5
def insert(intervals, new_interval):
  merged = []
  i, start, end = 0, 0, 1
  # skip (and add to output) all intervals that come before the 'new_interval'
  if(intervals[i][end] < new_interval[start]):
    print("Skip all the intervals that end before 'new_interval' starts.\nAdd these unchanged to the output list:")
  while i < len(intervals) and intervals[i][end] < new_interval[start]:
    print("\ti: " + str(i))
    print("\t\tintervals[i][end]: " + str(intervals[i][end]))
    print("\t\tnew_interval[start]: " + str(new_interval[start]))
    merged.append(intervals[i])
    print("\t\tMerged so far: "+ str(merged))
    i += 1
  return merged
def main():
  intervals_arr = [[[1, 3], [5, 7], [8, 12], [13, 14], [15, 20]], [[1, 3], [5, 7], [8, 12], [13, 14]],
  [[1, 3], [5, 7], [8, 12]],
  [[2, 3], [5, 7]]]
  new_intervals = [[7, 8], [8, 10], [4, 10], [1, 4]]
  for i in range(len(intervals_arr)):
      print("Inserting interval " + str(new_intervals[i]) + " in the intervals array: " + str(intervals_arr[i]) )
      result = insert(intervals_arr[i],new_intervals[i])   
      print("List with new interval inserted: " + str(result))
      print("-"*100 + "\n")
main()

In the code below, we merge the intervals that overlap the new interval and append the merged interval to the intervals occurring before it.

On lines 19-24, we update new_interval[start] and new_interval[end] if we find an interval that starts before new_interval[end].

On line 29, we append the newly constructed interval new_interval to the merged array.

Press + to interact
Python 3.5
def insert(intervals, new_interval):
  merged = []
  i, start, end = 0, 0, 1
  # skip (and add to output) all intervals that come before the 'new_interval'
  if(intervals[i][end] < new_interval[start]):
    print("Skip all the intervals that end before 'new_interval' starts.\nAdd these unchanged to the output list:")
  while i < len(intervals) and intervals[i][end] < new_interval[start]:
    print("\ti: " + str(i))
    print("\t\tintervals[i][end]: " + str(intervals[i][end]))
    print("\t\tnew_interval[start]: " + str(new_interval[start]))
    merged.append(intervals[i])
    print("\t\tMerged so far: "+ str(merged))
    i += 1
  # merge all intervals that overlap with 'new_interval'
  if(intervals[i][start] <= new_interval[end]):
    print("Merge all intervals that overlap with 'new_interval':")
  while i < len(intervals) and intervals[i][start] <= new_interval[end]:
    print("\t\ti: " + str(i))
    print("\t\tintervals[i][start]: " + str(intervals[i][start]))
    print("\t\tnew_interval[end]: " + str(new_interval[end]))
    new_interval[start] = min(intervals[i][start], new_interval[start])
    new_interval[end] = max(intervals[i][end], new_interval[end])
    i += 1
  # insert the new_interval
  print("\tInsert modified 'new_interval' ", str(new_interval), ":", sep="")
  merged.append(new_interval)
  print("\t\tMerged so far: "+ str(merged))
  
  return merged
def main():
  intervals_arr = [[[1, 3], [5, 7], [8, 12], [13, 14], [15, 20]], [[1, 3], [5, 7], [8, 12], [13, 14]],
  [[1, 3], [5, 7], [8, 12]],
  [[2, 3], [5, 7]]]
  new_intervals = [[7, 8], [8, 10], [4, 10], [1, 4]]
  for i in range(len(intervals_arr)):
      print("Inserting interval " + str(new_intervals[i]) + " in the intervals array: " + str(intervals_arr[i]) )
      result = insert(intervals_arr[i],new_intervals[i])   
      print("List with new interval inserted: " + str(result))
      print("-"*100 + "\n")
main()

The merged array contains the initial intervals and new interval so far. Now, we have to append the remaining intervals from the original intervals array.

In the code below, on lines 35-39, we append intervals[i] to the merged array.

Press + to interact
Python 3.5
def insert(intervals, new_interval):
  merged = []
  i, start, end = 0, 0, 1
  # skip (and add to output) all intervals that come before the 'new_interval'
  if(intervals[i][end] < new_interval[start]):
    print("Skip all the intervals that end before 'new_interval' starts.\nAdd these unchanged to the output list:")
  while i < len(intervals) and intervals[i][end] < new_interval[start]:
    print("\ti: " + str(i))
    print("\t\tintervals[i][end]: " + str(intervals[i][end]))
    print("\t\tnew_interval[start]: " + str(new_interval[start]))
    merged.append(intervals[i])
    print("\t\tMerged so far: "+ str(merged))
    i += 1
  # merge all intervals that overlap with 'new_interval'
  if(intervals[i][start] <= new_interval[end]):
    print("Merge all intervals that overlap with 'new_interval':")
  while i < len(intervals) and intervals[i][start] <= new_interval[end]:
    print("\t\ti: " + str(i))
    print("\t\tintervals[i][start]: " + str(intervals[i][start]))
    print("\t\tnew_interval[end]: " + str(new_interval[end]))
    new_interval[start] = min(intervals[i][start], new_interval[start])
    new_interval[end] = max(intervals[i][end], new_interval[end])
    i += 1
  # insert the new_interval
  print("\tInsert modified 'new_interval' ", str(new_interval), ":", sep="")
  merged.append(new_interval)
  print("\t\tMerged so far: "+ str(merged))
  # add all the remaining intervals to the output
  if(i < len(intervals)):
   print("Add all the remaining intervals to the output:")
  while i < len(intervals):
    merged.append(intervals[i])
    print("\ti: " + str(i))
    print("\tMerged so far: "+ str(merged))
    i += 1
  return merged
def main():
  intervals_arr = [[[1, 3], [5, 7], [8, 12], [13, 14], [15, 20]], [[1, 3], [5, 7], [8, 12], [13, 14]],
  [[1, 3], [5, 7], [8, 12]],
  [[2, 3], [5, 7]]]
  new_intervals = [[7, 8], [8, 10], [4, 10], [1, 4]]
  for i in range(len(intervals_arr)):
      print("Inserting interval " + str(new_intervals[i]) + " in the intervals array: " + str(intervals_arr[i]) )
      result = insert(intervals_arr[i],new_intervals[i])   
      print("List with new interval inserted: " + str(result))
      print("-"*100 + "\n")
main()