Merge Intervals

▶

Steps

setup

Check for empty input and sort intervals

The algorithm first checks if the input is empty. Then it sorts the intervals by their start times to prepare for merging.

💡 Sorting ensures intervals are in order, so overlapping intervals appear consecutively, simplifying merging.

Line:

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

💡 Sorting is a crucial preprocessing step that enables linear merging.

setup

Initialize index pointer to 0

Initialize 'index' to 0, pointing to the first interval which is the start of the merged intervals list.

💡 The 'index' pointer tracks the position of the last merged interval in the array.

Line:

index = 0

💡 'index' starts at 0 because the first interval is trivially merged by itself.

traverse

Start iterating from second interval (i=1)

Set 'i' to 1 to start comparing the second interval with the last merged interval at 'index'.

💡 We compare each new interval with the last merged to decide if they overlap or not.

Line:

for i in range(1, len(intervals)):

💡 Iteration begins from the second interval because the first is already considered merged.

compare

Compare intervals[1] start with intervals[index] end

Check if intervals[1][0] (2) is less than or equal to intervals[index][1] (3) to detect overlap.

💡 If the current interval starts before or at the end of last merged, they overlap and should merge.

Line:

if intervals[i][0] <= intervals[index][1]:

💡 Intervals [1,3] and [2,6] overlap, so they will be merged.

insert

Merge intervals by updating intervals[index][1]

Update the end of intervals[index] to max of intervals[index][1] and intervals[i][1], merging the two intervals.

💡 Merging extends the last merged interval to cover the current interval's end if larger.

Line:

intervals[index][1] = max(intervals[index][1], intervals[i][1])

💡 The merged interval becomes [1,6], combining the two overlapping intervals.

traverse

Move to next interval (i=2)

Increment 'i' to 2 to compare the third interval with the last merged interval at 'index'.

💡 We continue checking if the next interval overlaps with the merged intervals so far.

Line:

for i in range(1, len(intervals)):

💡 Iteration proceeds to the next interval for comparison.

compare

Compare intervals[2] start with intervals[index] end

Check if intervals[2][0] (8) is less than or equal to intervals[index][1] (6) to detect overlap.

💡 If current interval starts after last merged ends, no overlap occurs.

Line:

if intervals[i][0] <= intervals[index][1]:

💡 Intervals [1,6] and [8,10] do not overlap, so we must move 'index' and copy the current interval.

insert

Increment index and copy intervals[i] to intervals[index]

Since no overlap, move 'index' forward and copy the current interval to that position.

💡 This step adds a new merged interval to the list at the next position.

Line:

index += 1
intervals[index] = intervals[i]

💡 The merged intervals list now includes [1,6] and [8,10] at positions 0 and 1.

traverse

Move to next interval (i=3)

Increment 'i' to 3 to compare the fourth interval with the last merged interval at 'index'.

💡 We continue checking if the next interval overlaps with the merged intervals so far.

Line:

for i in range(1, len(intervals)):

💡 Iteration proceeds to the next interval for comparison.

compare

Compare intervals[3] start with intervals[index] end

Check if intervals[3][0] (15) is less than or equal to intervals[index][1] (10) to detect overlap.

💡 If current interval starts after last merged ends, no overlap occurs.

Line:

if intervals[i][0] <= intervals[index][1]:

💡 Intervals [8,10] and [15,18] do not overlap, so we must move 'index' and copy the current interval.

insert

Increment index and copy intervals[i] to intervals[index]

Since no overlap, move 'index' forward and copy the current interval to that position.

💡 This step adds the last interval to the merged list.

Line:

index += 1
intervals[index] = intervals[i]

💡 The merged intervals list now includes [1,6], [8,10], and [15,18].

reconstruct

Iteration complete, return merged intervals slice

The loop ends, and the algorithm returns the slice of intervals up to index+1 as the merged result.

💡 Only the first index+1 intervals are valid merged intervals; the rest are leftover copies.

Line:

return intervals[:index+1]

💡 The final merged intervals are [[1,6],[8,10],[15,18]].

def merge(intervals):
    # STEP 1: Check empty and sort
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])

    # STEP 2: Initialize index
    index = 0

    # STEP 3: Iterate from second interval
    for i in range(1, len(intervals)):
        # STEP 4: Compare start of current with end of last merged
        if intervals[i][0] <= intervals[index][1]:
            # STEP 5: Merge intervals by updating end
            intervals[index][1] = max(intervals[index][1], intervals[i][1])
        else:
            # STEP 8 & 11: No overlap, move index and copy current
            index += 1
            intervals[index] = intervals[i]

    # STEP 12: Return merged intervals slice
    return intervals[:index+1]

if __name__ == '__main__':
    intervals = [[1,3],[2,6],[8,10],[15,18]]
    print(merge(intervals))

📊

Merge Intervals - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand exactly how intervals are merged in-place without extra space.

setup

0

1

2

3

setup

index

0

1

2

3

move_right

index

0

i

1

2

3

compare

index

0

i

1

2

3

insert

index

0

i

1

2

3

move_right

index

0

1

i

2

3

compare

index

0

1

i

2

3

insert

0

index

1

i

2

3

move_right

0

index

1

2

i

3

compare

0

index

1

2

i

3

insert

0

1

index

2

i

3

record

0

1

index

2

3

Result: [[1,6],[8,10],[15,18]]

Key Takeaways

✓ Sorting intervals by start time is essential to enable linear merging.

Without sorting, overlapping intervals could be scattered, making merging complex.

✓ The 'index' pointer tracks the last merged interval, allowing in-place merging without extra space.

This pointer movement shows how the algorithm compacts merged intervals at the front.

✓ Overlapping intervals are merged by extending the end time, while non-overlapping intervals advance the 'index' and are copied.

Seeing this decision visually clarifies when intervals combine versus when a new merged interval starts.

Practice

1. You are given a list of meeting time intervals represented as pairs of start and end times. You need to determine if a single person can attend all meetings without any overlaps. Which approach guarantees an optimal and efficient solution?

easy

A. Use dynamic programming to find the maximum number of non-overlapping intervals.

B. Sort intervals by start time and check for any overlap by comparing each interval's start with the previous interval's end.

C. Use a brute force nested loop to compare every pair of intervals for overlap.

D. Sort intervals by end time and greedily select intervals that finish earliest to maximize the number of meetings attended.

Solution

1. Step 1: Understand the problem requirement

   The problem asks if a single person can attend all meetings without overlap, so we must check if any intervals overlap.

2. Step 2: Identify the correct approach

   Sorting intervals by start time and checking if any interval starts before the previous one ends guarantees detection of overlaps efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting by start time and checking overlaps is the standard approach [OK]

Hint: Sort by start time and check overlaps [OK]

Common Mistakes:

• Confusing sorting by end time with start time for overlap detection

2. Given a list of train arrival and departure times, you need to find the minimum number of platforms required so that no train waits. Which approach guarantees an optimal solution for this problem?

easy

A. Use a greedy algorithm that assigns platforms as trains arrive without sorting times.

B. Use a sweep line algorithm by creating events for arrivals and departures, sorting them, and tracking concurrent trains.

C. Use dynamic programming to find the maximum overlap of intervals by building a state table.

D. Use nested loops to check every pair of trains for overlap and count maximum overlaps.

Solution

1. Step 1: Understand the problem requires tracking concurrent trains

   The key is to find the maximum number of trains present at the station simultaneously.

2. Step 2: Recognize that sorting events and sweeping through them tracks concurrency efficiently

   By creating arrival and departure events and sorting them, we can increment or decrement the count of trains present, capturing the peak count.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sweep line tracks concurrency optimally [OK]

Hint: Sort events and sweep to track concurrency [OK]

Common Mistakes:

• Assuming greedy assignment without sorting works
• Trying DP which is unnecessary overhead
• Using nested loops which is inefficient

3. Given the following code and input intervals = [[1,4],[3,6],[2,8]], what is the value of count after the loop finishes?

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Sort intervals by start ascending, end descending

   Sorted intervals: [[1,4],[2,8],[3,6]]

2. Step 2: Iterate and update count and max_end

   Iteration 1: end=4 > max_end=0 -> count=1, max_end=4 Iteration 2: end=8 > max_end=4 -> count=2, max_end=8 Iteration 3: end=6 ≤ max_end=8 -> count unchanged

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count increments twice for uncovered intervals [OK]

Hint: Sort then count intervals with strictly greater end [OK]

Common Mistakes:

• Misorder intervals after sorting
• Off-by-one counting in loop

4. The following code attempts to find the maximum number of non-overlapping intervals. Which line contains a subtle bug that can cause incorrect results on some inputs?

def max_non_overlapping_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    removals = 0
    last_end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] <= last_end:
            removals += 1
            last_end = min(last_end, intervals[i][1])
        else:
            last_end = intervals[i][1]
    return len(intervals) - removals

medium

A. Line 9: Updating last_end to intervals[i][1] when no overlap

B. Line 2: Sorting intervals by start time instead of end time

C. Line 7: Updating last_end to min(last_end, intervals[i][1]) inside overlap condition

D. Line 5: Using '<=' instead of '<' in the overlap condition

Solution

1. Step 1: Understand overlap condition

   Intervals that start exactly at last_end do not overlap and should be allowed.

2. Step 2: Identify incorrect operator

   Using '<=' causes intervals starting exactly at last_end to be considered overlapping, reducing count incorrectly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Change '<=' to '<' fixes the bug [OK]

Hint: Overlap check must use strict less than, not less or equal [OK]

Common Mistakes:

• Confusing inclusive vs exclusive overlap conditions
• Sorting by start time is allowed but less optimal
• Incorrect last_end updates

5. Suppose the problem changes: intervals can be reused infinitely many times, and you want to count how many intervals contain each point considering unlimited reuse (e.g., intervals repeat periodically). Which modification to the line sweep approach correctly handles this scenario?

hard

A. No change needed; line sweep already counts intervals correctly regardless of reuse.

B. Preprocess intervals to merge overlapping intervals into one, then run line sweep once.

C. Use a segment tree or binary indexed tree to handle repeated intervals efficiently instead of line sweep.

D. Modify events to include multiple copies of intervals explicitly and run line sweep on expanded events.

Solution

1. Step 1: Understand reuse impact

   Infinite reuse means intervals repeat periodically, so naive line sweep with explicit events cannot handle infinite copies.

2. Step 2: Recognize data structure need

   Segment trees or binary indexed trees can efficiently query counts over ranges and handle repeated intervals without enumerating all copies.

3. Step 3: Why other options fail

   No change (A) ignores infinite reuse; merging (B) loses count detail; explicit expansion (D) is infeasible for infinite repeats.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Segment trees handle range queries with repeated intervals efficiently [OK]

Hint: Infinite reuse requires data structures, not event enumeration [OK]

Common Mistakes:

• Assuming line sweep handles infinite repeats
• Trying to expand events explicitly
• Merging intervals loses count accuracy