Non-overlapping Intervals (Max Non-Overlap)

▶

Steps

setup

Sort intervals by start time

The intervals are sorted by their start times to process them in chronological order.

💡 Sorting ensures we consider intervals in the order they begin, which is essential for the greedy approach.

Line:

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

💡 Sorting by start time sets the stage for comparing intervals sequentially.

setup

Initialize removals and last_end

Initialize removal count to 0 and set last_end to the end of the first interval.

💡 Tracking removals and last_end helps decide which intervals to keep or remove.

Line:

removals = 0
last_end = intervals[0][1]

💡 Starting with the first interval kept, last_end marks the boundary for overlap checks.

traverse

Move to second interval

Move pointer 'i' to the second interval to check for overlap with last_end.

💡 We check each interval in order to decide if it overlaps with the last kept interval.

Line:

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

💡 Advancing the pointer allows sequential overlap checks.

compare

Compare second interval start with last_end

Check if the start of interval [2,4] is less than last_end (3), indicating overlap.

💡 Detecting overlap is key to deciding whether to remove an interval.

Line:

if intervals[i][0] < last_end:

💡 The second interval overlaps with the first, so a removal decision is needed.

shrink

Increment removals and update last_end to min end

Since intervals overlap, increment removals and update last_end to the smaller end time between last_end and current interval's end.

💡 Choosing the interval with the smaller end time keeps more room for future intervals.

Line:

removals += 1
last_end = min(last_end, intervals[i][1])

💡 Keeping the interval that ends earlier reduces future overlaps.

traverse

Move to third interval

Advance pointer 'i' to the third interval [3,5] to check for overlap.

💡 We continue checking intervals one by one for overlaps.

Line:

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

💡 Sequential traversal ensures all intervals are considered.

compare

Compare third interval start with last_end

Check if the start of interval [3,5] is less than last_end (3), to detect overlap.

💡 Overlap check determines if removal is needed.

Line:

if intervals[i][0] < last_end:

💡 No overlap means we can keep this interval safely.

expand

Update last_end to third interval's end

Since no overlap, update last_end to the end of the current interval (5).

💡 Updating last_end sets the new boundary for future overlap checks.

Line:

else:
    last_end = intervals[i][1]

💡 Extending last_end means the current interval is kept.

reconstruct

End of iteration, compute max non-overlapping intervals

Calculate the maximum number of non-overlapping intervals by subtracting removals from total intervals.

💡 The final answer is total intervals minus how many we removed to avoid overlaps.

Line:

return len(intervals) - removals

💡 This formula gives the maximum count of intervals that do not overlap.

final

Final answer: 2 non-overlapping intervals

The algorithm returns 2, meaning we can keep two intervals without overlap.

💡 This confirms the greedy approach successfully maximizes non-overlapping intervals.

💡 The intervals [1,3] and [3,5] are chosen as the optimal non-overlapping set.

from typing import List

def max_non_overlapping_intervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[0])  # STEP 1: sort intervals by start
    removals = 0  # STEP 2: initialize removals
    last_end = intervals[0][1]  # STEP 2: initialize last_end
    for i in range(1, len(intervals)):  # STEP 3: traverse intervals
        if intervals[i][0] < last_end:  # STEP 4: check overlap
            removals += 1  # STEP 5: increment removals
            last_end = min(last_end, intervals[i][1])  # STEP 5: update last_end
        else:
            last_end = intervals[i][1]  # STEP 8: update last_end when no overlap
    return len(intervals) - removals  # STEP 9: compute result

if __name__ == '__main__':
    intervals = [[1,3],[2,4],[3,5]]
    print(max_non_overlapping_intervals(intervals))  # Output: 2

📊

Non-overlapping Intervals (Max Non-Overlap) - Watch the Algorithm Execute, Step by Step

Watching each comparison and pointer update helps you understand how the greedy choice is made to keep intervals with the earliest end time, which is key to maximizing non-overlapping intervals.

move_right

[1,3]

0

[2,4]

1

[3,5]

2

record

i

[1,3]

0

[2,4]

1

[3,5]

2

Result: 0

move_right

[1,3]

0

i

[2,4]

1

[3,5]

2

Result: 0

compare

[1,3]

0

i

[2,4]

1

[3,5]

2

Result: 0

shrink

[1,3]

0

i

[2,4]

1

[3,5]

2

Result: 1

move_right

[1,3]

0

[2,4]

1

i

[3,5]

2

Result: 1

compare

[1,3]

0

[2,4]

1

i

[3,5]

2

Result: 1

move_right

[1,3]

0

[2,4]

1

i

[3,5]

2

Result: 1

record

[1,3]

0

[2,4]

1

[3,5]

2

Result: 2

record

[1,3]

0

[2,4]

1

[3,5]

2

Result: 2

Key Takeaways

✓ Sorting intervals by start time allows sequential overlap checks.

Without sorting, the algorithm cannot reliably detect overlaps in order.

✓ When intervals overlap, removing the one with the later end time maximizes future interval inclusion.

This greedy choice is subtle and best understood visually by seeing last_end update.

✓ The final answer is total intervals minus removals, representing the maximum non-overlapping set.

This formula is simple but the reasoning behind removals is clearer when traced step-by-step.

Practice

1. You are given a list of non-overlapping intervals sorted by their start times, and a new interval to insert. Which approach guarantees an optimal solution that correctly merges overlapping intervals after insertion?

easy

A. Use a greedy approach that inserts the new interval at the end and merges overlapping intervals in one pass without sorting.

B. Iterate through intervals and insert the new interval in the correct position without sorting, then merge overlapping intervals.

C. Use dynamic programming to find the minimal set of merged intervals after insertion.

D. Append the new interval, sort all intervals by start time, then merge overlapping intervals in one pass.

Solution

1. Step 1: Understand the problem constraints

   The intervals are sorted and non-overlapping initially, but inserting a new interval may cause overlaps.

2. Step 2: Identify the approach that guarantees correct merging

   Appending and then sorting ensures the new interval is placed correctly relative to others, allowing a single pass merge to handle all overlaps reliably.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting after insertion ensures correct order for merging [OK]

Hint: Sort after insertion to guarantee correct merge order [OK]

Common Mistakes:

• Assuming intervals remain sorted after insertion without sorting
• Trying to merge without sorting leads to missed overlaps
• Using DP unnecessarily complicates the problem

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. What is the time complexity of the optimal greedy algorithm that sorts balloons by their end coordinate and then iterates once to find the minimum number of arrows?

medium

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

Solution

1. Step 1: Identify sorting cost

   Sorting n intervals by end coordinate takes O(n log n) time.

2. Step 2: Identify iteration cost

   Single pass through sorted intervals is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Dominant cost is sorting, so total is O(n log n) [OK]

Hint: Sorting dominates; iteration is linear [OK]

Common Mistakes:

• Assuming linear time because of single pass
• Confusing with brute force O(n^2)
• Ignoring sorting cost

4. Suppose the problem is extended so that numbers can be added multiple times (duplicates allowed), and the intervals must reflect the count of each number (e.g., intervals store counts of coverage). Which modification to the optimal balanced tree approach is necessary to handle this correctly?

hard

A. Augment intervals with counts and update counts on insertion; merge intervals only if counts allow.

B. Keep the current approach but ignore duplicates since intervals are disjoint sets.

C. Use a brute force approach storing all numbers and recomputing intervals with counts on each query.

D. Replace balanced tree with a hash map keyed by number to track counts and intervals separately.

Solution

1. Step 1: Understand the impact of duplicates

   Intervals must now track counts, so simple presence is insufficient.

2. Step 2: Modify data structure

   Intervals should store counts per interval or per number; merging must consider counts to avoid losing duplicates.

3. Step 3: Evaluate options

   Ignoring duplicates (B) breaks correctness. Brute force (C) is inefficient. Hash map (D) loses interval ordering benefits. Augmenting intervals with counts (A) preserves efficiency and correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Counting duplicates requires augmenting intervals [OK]

Hint: Track counts in intervals to handle duplicates correctly [OK]

Common Mistakes:

• Ignoring duplicates
• Using brute force for counts
• Losing interval order with hash maps

5. Suppose balloons can be reused multiple times after bursting (i.e., an arrow can burst a balloon multiple times if shot at different points). How does this affect the algorithm to find the minimum number of arrows needed?

hard

A. The original greedy algorithm still applies without changes.

B. We must use dynamic programming to track multiple bursts per balloon.

C. The problem reduces to counting unique balloons since reuse removes overlap constraints.

D. We can shoot arrows only at balloon start points to minimize arrows.

Solution

1. Step 1: Understand reuse effect

   If balloons can be burst multiple times independently, overlapping intervals no longer reduce arrow count.

2. Step 2: Simplify problem

   Each balloon requires at least one arrow, so minimum arrows equal number of unique balloons.

3. Step 3: Algorithm implication

   Overlap and interval sorting become irrelevant; counting balloons suffices.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Reuse breaks overlap optimization, so count balloons directly [OK]

Hint: Reuse removes overlap benefit; count balloons directly [OK]

Common Mistakes:

• Assuming greedy still works unchanged
• Trying to track multiple bursts with DP unnecessarily
• Ignoring that reuse breaks interval overlap logic