We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Insert Interval

Difficulty: Medium

Problem Description

You are given an array of non-overlapping intervals where intervals[i] = [start_i, end_i] represent the start and the end of the i-th interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion.

Key Insights

  • The input intervals are sorted, which allows for efficient searching and merging.
  • Merging involves checking for overlaps between intervals and adjusting endpoints.
  • We can iterate through the list of intervals, comparing each to the new interval to determine where overlaps occur.

Space and Time Complexity

Time Complexity: O(n), where n is the number of intervals. We may need to traverse the entire list in the worst case. Space Complexity: O(n), as we may create a new list to store the merged intervals.

Solution

To solve the problem, we can use the following approach:

  1. Initialize a new list to hold the resulting intervals.
  2. Iterate through the existing intervals:
    • If the current interval ends before the new interval starts, add the current interval to the result.
    • If the current interval starts after the new interval ends, add the new interval to the result and set it to be merged.
    • If there is an overlap, update the new interval's start and end to be the minimum start and maximum end of the overlapping intervals.
  3. Finally, add the last updated new interval to the result.

The algorithm primarily utilizes a list to store the merged intervals.

Code Solutions

def insert(intervals, newInterval):
    result = []
    i = 0
    n = len(intervals)

    # Add all intervals before the newInterval
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Merge overlapping intervals
    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

    # Add the merged newInterval
    result.append(newInterval)

    # Add all remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1

    return result
← Back to All Questions