Insert Interval

Clarify the problem:

• The problem requires inserting a new interval into a sorted list of non-overlapping intervals.
• We need to implement a function that takes a list of intervals and a new interval as input and returns a modified list of intervals after inserting the new interval.

Analyze the problem:

• Input: A list of intervals represented as a list of pairs [start, end], where start and end are integers.
• Output: A modified list of intervals after inserting the new interval.
• Constraints:
  • The input list of intervals is sorted in ascending order based on the start time.
  • The input intervals do not overlap with each other.
  • The new interval may overlap with existing intervals.

Design an algorithm:

• We can iterate over the intervals and find the correct position to insert the new interval.
• We need to consider different cases where the new interval can be merged with existing intervals or inserted in between intervals.
• We will keep track of the merged intervals and append the remaining intervals after the new interval.
• Finally, we will return the modified list of intervals.

Explain your approach:

• We will implement a function called insertInterval to solve the problem.
• The function will take a list of intervals, intervals, and a new interval, newInterval, as input.
• We will initialize an empty list called mergedIntervals to store the merged intervals.
• We will iterate over each interval in the input list and compare it with the new interval.
• We will handle different cases:
  • If the current interval ends before the new interval starts, we can append it directly to the mergedIntervals.
  • If the current interval starts after the new interval ends, it means we have found the position to insert the new interval. We will append the new interval and all the remaining intervals to the mergedIntervals.
  • If the current interval overlaps with the new interval, we will merge them by updating the start and end times of the new interval.
• Finally, we will return the mergedIntervals.

Write clean and readable code:

python

def insertInterval(intervals, newInterval):
    mergedIntervals = []
    i = 0
    n = len(intervals)

    # Append intervals that end before newInterval starts
    while i < n and intervals[i][1] < newInterval[0]:
        mergedIntervals.append(intervals[i])
        i += 1

    # Merge intervals that overlap with newInterval
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1

    # Append the merged interval
    mergedIntervals.append(newInterval)

    # Append remaining intervals
    while i < n:
        mergedIntervals.append(intervals[i])
        i += 1

    return mergedIntervals

Test your code:

python

# Test case 1
intervals = [[1, 3], [6, 9]]
newInterval = [2, 5]
# After inserting the new interval, the intervals become [[1, 5], [6, 9]]
assert insertInterval(intervals, newInterval) == [[1, 5], [6, 9]]

# Test case 2
intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]
newInterval = [4, 8]
# After inserting the new interval, the intervals become [[1, 2], [3, 10], [12, 16]]
assert insertInterval(intervals, newInterval) == [[1, 2], [3, 10], [12, 16]]

# Test case 3
intervals = []
newInterval = [1, 3]
# After inserting the new interval, the intervals become [[1, 3]]
assert insertInterval(intervals, newInterval) == [[1, 3]]

The code has been tested with multiple test cases, including cases with different intervals and new intervals. The output for each test case matches the expected results.

Optimize if necessary:

• The current solution has a time complexity of O(N), where N is the number of intervals in the input list.
• We iterate over each interval once to find the correct position to insert the new interval and merge overlapping intervals.
• The space complexity is O(N) as we use the mergedIntervals list to store the modified intervals.

Handle error cases:

• The code assumes that the input intervals are valid and sorted in ascending order based on the start time.
• The code handles the case when the input list is empty and returns a list with only the new interval.

Discuss complexity analysis:

• Let N be the number of intervals in the input list.
• The time complexity of the solution is O(N) as we iterate over each interval once.
• The space complexity is also O(N) as we store the modified intervals in a separate list.
• The code does not involve any significant trade-offs as it solves the problem optimally.