Insert Interval

To solve this coding challenge, we need to insert a new interval into an existing array of non-overlapping intervals while making sure that the merged result is still a set of non-overlapping intervals, sorted by their start times. Let's break down the steps comprehensively.

Explanation

Goal

Given an array of non-overlapping intervals sorted in ascending order by their start times, and a new interval, we want to insert this new interval into the array while maintaining the order and ensuring no overlapping exists. The solution has to:

1. Traverse the existing intervals.
2. Determine where the new interval can fit without causing any overlaps.
3. Merge intervals if there are any overlaps.
4. Add all intervals (including the merged new interval) to the result array and return it.

Strategy

5. Initialization and Result Preparation:
• Prepare an empty list to store the resulting intervals after insertion.
• Use a pointer to traverse through the given intervals.
6. First Part - Before New Interval:
• First, we need to add all intervals that end before the new interval starts. These intervals don't overlap with the new interval and can be added directly to the output list.
7. Second Part - Merging Overlapping Intervals:
• For intervals that overlap with the new interval, we merge them. The merging is done by comparing start and end times to ensure the entire span of overlap is captured within a single interval.
8. Third Part - After New Interval:
• Add the remaining intervals that start after the new interval ends. These intervals also don't overlap with the new interval and can be added directly to the output list.
9. Return the Result List:
• Finally, the result list which contains the merged intervals is returned.

Detailed Steps in Pseudocode

10. Initialize an empty list
    result
    for the final merged intervals.
11. Initialize pointer
    i
    to 0.
12. Add intervals before newInterval without overlapping:
• While
  i
  is less than the length of intervals and the end of the interval at index
  i
  is less than the start of
  newInterval
  , add the interval at index
  i
  to
  result
  and increment
  i
  .
13. Merge overlapping intervals with newInterval:
• While
  i
  is less than the length of intervals and the start of the interval at index
  i
  is less than or equal to the end of
  newInterval
  , compute the new merged interval by taking the minimum start and maximum end from both the current interval and
  newInterval
  . Update
  newInterval
  and increment
  i
  .
14. Add newInterval after merging overlaps:
• Add
  newInterval
  to
  result
  .
15. Add remaining intervals after newInterval without overlapping:
• While
  i
  is less than the length of intervals, add the interval at index
  i
  to
  result
  and increment
  i
  .
16. Return the
    result
    .

Pseudocode

                                            
# Initialize result list
result = []

# Initialize index pointer i to 0
i = 0

# Step 1: Add all intervals before newInterval
while i < length of intervals AND intervals[i][1] < newInterval[0]:
    add intervals[i] to result
    increment i

# Step 2: Merge overlapping intervals with newInterval
while i < length of intervals AND intervals[i][0] <= newInterval[1]:
    newInterval[0] = min(newInterval[0], intervals[i][0])
    newInterval[1] = max(newInterval[1], intervals[i][1])
    increment i

# Add the merged newInterval to result
add newInterval to result

# Step 3: Add all remaining intervals after newInterval
while i < length of intervals:
    add intervals[i] to result
    increment i

# Return the result list containing merged intervals
return result

                                        

Comprehensive Walkthrough

• Initialize
  result
  and
  i
  .
• Traverse the intervals and add non-overlapping intervals to the
  result
  .
• Merge overlapping intervals with the new one.
• Add the merged interval into the
  result
  .
• Append rest intervals which come after the merged interval.

This method ensures that the time complexity is linear,

O(n)

, which efficiently handles even the upper constraint limit of the intervals list size.