Insert Interval

TIP102 Unit 1 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Sorting, Merging Intervals

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the function?

  • A: The input consists of a list of non-overlapping intervals intervals, sorted in ascending order, and a new interval new_interval that needs to be inserted.

• Q: What is the expected output of the function?

  • A: The function should return a new list of intervals where the new_interval has been inserted and any overlapping intervals have been merged.

• Q: What does it mean for intervals to overlap?

  • A: Two intervals [a, b] and [c, d] overlap if b >= c and a <= d. Overlapping intervals should be merged into a single interval.

• Q: What if the new interval does not overlap with any existing interval?

  • A: If the new interval does not overlap with any existing interval, it should be inserted in its correct position based on the start time.

• Q: What should the function return if intervals is empty?

  • A: If intervals is empty, the function should return a list containing just the new_interval.

• The function insert_interval() should insert a new interval into a list of non-overlapping intervals and merge any overlapping intervals.

HAPPY CASE
Input: intervals = [[1, 3], [6, 9]], new_interval = [2, 5]
Expected Output: [[1, 5], [6, 9]]

UNHAPPY CASE
Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], new_interval = [4, 8]
Expected Output: [[1, 2], [3, 10], [12, 16]]

EDGE CASE
Input: intervals = [], new_interval = [5, 7]
Expected Output: [[5, 7]]

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Iterate through the existing intervals and handle them based on their relation to the new interval.

1. Initialize an empty list `merged` to store the resulting intervals.
2. Initialize an index `i` to 0 and get the length `n` of `intervals`.
3. Add all intervals that end before the new interval starts to `merged`.
4. Merge intervals that overlap with the new interval:
   a. Update the start and end of the new interval based on the overlapping intervals.
5. Append the merged new interval to `merged`.
6. Add any remaining intervals to `merged`.
7. Return `merged`

⚠️ Common Mistakes

• Failing to properly merge overlapping intervals.
• Not handling edge cases like inserting into an empty list or merging at the beginning or end.

I-mplement

Implement the code to solve the algorithm.

def insert_interval(intervals, new_interval):
    merged = []
    i = 0
    n = len(intervals)

    # Add all intervals that come before the new interval
    while i < n and intervals[i][1] < new_interval[0]:
        merged.append(intervals[i])
        i += 1

    # Merge intervals that overlap with the new interval
    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    merged.append(new_interval)

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

    return merged