Insert Interval

▶

Steps

setup

Start with initial intervals

We begin with the original intervals array [[1,3],[6,9]] and the new interval [2,5] ready to be inserted.

💡 Knowing the starting data is essential before any changes happen.

Line:

intervals = [[1,3],[6,9]]
newInterval = [2,5]

💡 The initial intervals are sorted and non-overlapping.

insert

Append the new interval

The new interval [2,5] is appended to the intervals list, making it [[1,3],[6,9],[2,5]].

💡 Appending is the first step to include the new interval before sorting and merging.

Line:

intervals.append(newInterval)

💡 Appending adds the new interval but does not guarantee order or merging yet.

expand

Sort intervals by start time

Sort the intervals by their start times to get [[1,3],[2,5],[6,9]].

💡 Sorting ensures intervals are in order to merge overlapping ones correctly.

Line:

intervals.sort(key=lambda x: x[0])

💡 Sorting places intervals in ascending order by start time.

setup

Initialize merged list with first interval

Start the merged list with the first interval [1,3].

💡 The merged list will accumulate merged intervals starting from the first sorted interval.

Line:

merged = [intervals[0]]

💡 The first interval is the base for merging subsequent intervals.

compare

Compare intervals[1] start with merged[-1] end

Check if intervals[1] = [2,5] overlaps with merged[-1] = [1,3] by comparing 2 <= 3.

💡 This comparison determines if intervals should be merged or appended separately.

Line:

if intervals[i][0] <= merged[-1][1]:

💡 Since 2 <= 3, the intervals overlap and must be merged.

merge

Merge overlapping intervals

Update merged[-1] end to max(3,5) = 5, merging [1,3] and [2,5] into [1,5].

💡 Merging combines overlapping intervals into one with the earliest start and latest end.

Line:

merged[-1][1] = max(merged[-1][1], intervals[i][1])

💡 The merged interval now covers the full range of both overlapping intervals.

traverse

Move to next interval

Increment i to 2 to examine the next interval [6,9].

💡 Moving forward allows checking all intervals for possible merges.

Line:

for i in range(1, len(intervals)):  # i=2 now

💡 The algorithm processes intervals sequentially.

compare

Compare intervals[2] start with merged[-1] end

Check if intervals[2] = [6,9] overlaps with merged[-1] = [1,5] by comparing 6 <= 5.

💡 This comparison decides if the current interval merges or is separate.

Line:

if intervals[i][0] <= merged[-1][1]:

💡 Since 6 > 5, intervals do not overlap and [6,9] is appended.

insert

Append non-overlapping interval

Append intervals[2] = [6,9] to merged list, now merged = [[1,5],[6,9]].

💡 Appending keeps intervals separate when they do not overlap.

Line:

merged.append(intervals[i])

💡 The merged list grows with non-overlapping intervals preserved.

reconstruct

End of intervals, return merged list

All intervals processed; return the merged list [[1,5],[6,9]] as the final answer.

💡 Returning the merged list completes the algorithm.

Line:

return merged

💡 The final merged intervals represent the correct insertion and merging.

from typing import List

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    intervals.append(newInterval)  # STEP 2
    intervals.sort(key=lambda x: x[0])  # STEP 3
    merged = [intervals[0]]  # STEP 4
    for i in range(1, len(intervals)):  # STEP 7
        if intervals[i][0] <= merged[-1][1]:  # STEP 5 and 8
            merged[-1][1] = max(merged[-1][1], intervals[i][1])  # STEP 6
        else:
            merged.append(intervals[i])  # STEP 9
    return merged  # STEP 10

📊

Insert Interval - Watch the Algorithm Execute, Step by Step

Watching each operation helps you understand how intervals are combined and why sorting is crucial before merging.

none

0

1

Result: []

insert

0

1

2

Result: []

move_left

0

1

2

Result: []

record

0

i

1

2

Result: [[1,3]]

compare

0

i

1

2

Result: [[1,3]]

swap

0

i

1

2

Result: [[1,5]]

move_right

0

1

i

2

Result: [[1,5]]

compare

0

1

i

2

Result: [[1,5]]

record

0

1

i

2

Result: [[1,5],[6,9]]

none

0

1

2

Result: [[1,5],[6,9]]

Key Takeaways

✓ Appending the new interval and sorting is crucial before merging.

Without sorting, merging overlapping intervals would be incorrect or impossible.

✓ Merging happens only when intervals overlap, detected by comparing start and end points.

This step-by-step comparison clarifies when intervals combine or stay separate.

✓ The merged list grows dynamically, either updating the last interval or appending a new one.

Seeing the merged list update visually helps understand the algorithm's incremental construction.

Practice

1. Given multiple employees' schedules with intervals representing their busy times, which algorithmic approach guarantees finding all common free time intervals where no employee is busy?

easy

A. Greedy interval scheduling that picks earliest finishing intervals

B. Dynamic programming to find maximum non-overlapping intervals

C. Sweep line / event processing that tracks interval start and end events

D. Brute force checking every time point across all intervals

Solution

1. Step 1: Understand problem requires identifying gaps where no intervals overlap

   Greedy scheduling or DP focus on selecting intervals, not gaps between them.

2. Step 2: Sweep line processes all start/end events in order, tracking active intervals to find free gaps

   This approach efficiently detects when no employee is busy, yielding correct free times.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sweep line tracks active intervals and finds free gaps [OK]

Hint: Sweep line tracks interval endpoints to find free gaps [OK]

Common Mistakes:

• Assuming greedy or DP can find free gaps directly

2. What is the time complexity of the addNum operation in the optimal balanced tree approach for maintaining disjoint intervals, assuming there are n intervals stored?

medium

A. O(n) because intervals need to be scanned linearly for merging

B. O(log n) due to binary search and limited merging operations

C. O(n log n) because each insertion requires sorting intervals

D. O(1) since insertion is always at the end or start

Solution

1. Step 1: Identify main operations in addNum

   addNum uses binary search (bisect_left) to find insertion index in O(log n).

2. Step 2: Analyze merging cost

   Merging involves at most constant number of interval merges (left, right, or both), so O(1) extra work.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search dominates, merges are constant time [OK]

Hint: Binary search + constant merges -> O(log n) [OK]

Common Mistakes:

• Assuming linear scan for merging
• Confusing sorting cost per insertion
• Ignoring constant merge steps

3. Examine the following buggy code for the Meeting Rooms II problem. Which line contains the subtle bug that can cause incorrect room count?

medium

A. Line 3: Missing check for empty intervals list.

B. Line 9: Incorrect condition using >= instead of > for overlap.

C. Line 11: Using heappush without popping first.

D. Line 6: Intervals are not sorted before processing.

Solution

1. Step 1: Identify missing sorting.

   Intervals must be sorted by start time before heap processing; missing this breaks heap logic.

2. Step 2: Confirm other lines.

   Empty check is present; condition >= is correct for allowing room reuse; pushing after popping is correct.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Without sorting, heap logic fails to track earliest ending meeting [OK]

Hint: Heap logic requires sorted intervals by start time [OK]

Common Mistakes:

• Confusing overlap condition with <=
• Forgetting to sort intervals
• Misordering heap push/pop

4. Suppose the car pooling problem is modified so that trips can overlap and passengers can be picked up and dropped off multiple times (i.e., trips can reuse the same passengers). Which of the following algorithmic changes correctly adapts the solution to handle this variant efficiently?

hard

A. Use a segment tree or binary indexed tree to efficiently update and query passenger counts over intervals

B. Switch to a priority queue to process events in order and track current passengers dynamically

C. Use the same difference array approach but multiply passenger counts by the number of trips to simulate reuse

D. Modify the difference array to allow negative passenger counts and track net changes carefully

Solution

1. Step 1: Understand reuse complexity

   Reusing passengers means overlapping intervals can increase and decrease counts multiple times, requiring efficient range updates and queries.

2. Step 2: Identify suitable data structure

   Segment trees or binary indexed trees support efficient interval updates and queries, handling overlapping intervals with reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Segment trees handle dynamic interval sums efficiently [OK]

Hint: Reuse -> need data structure for interval updates [OK]

Common Mistakes:

• Multiplying counts breaks logic
• Priority queue alone can't handle reuse efficiently
• Allowing negative counts without structure causes errors

5. Suppose the meeting intervals can be reused multiple times (i.e., a meeting can be attended multiple times if no overlaps occur). Which modification to the algorithm is necessary to correctly determine if a person can attend all meetings without overlap?

hard

A. Sort intervals by end time and greedily select intervals to maximize non-overlapping meetings.

B. No change needed; the original algorithm already handles reuse correctly.

C. Use a frequency map to count how many times each interval appears and check overlaps accordingly.

D. Sort intervals by start time and check overlaps as before, but also track counts of repeated intervals.

Solution

1. Step 1: Understand reuse scenario

   Reusing intervals means attending multiple instances of the same meeting, so we want to maximize the number of non-overlapping meetings.

2. Step 2: Identify correct approach

   Sorting by end time and greedily selecting earliest finishing meetings maximizes non-overlapping intervals, handling reuse correctly.

3. Step 3: Why other options fail

   Original algorithm only checks if all intervals can be attended once; frequency maps or tracking counts do not solve scheduling conflicts optimally.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Greedy by end time is classic interval scheduling for maximum non-overlapping intervals [OK]

Hint: Reuse requires interval scheduling by end time [OK]

Common Mistakes:

• Assuming original overlap check suffices for reuse
• Trying to track counts without scheduling logic