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?

medium🐞 Bug Identification Q14 of Q15

Intervals - Non-overlapping Intervals (Max Non-Overlap)

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

ALine 9: Updating last_end to intervals[i][1] when no overlap

BLine 2: Sorting intervals by start time instead of end time

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

DLine 5: Using '<=' instead of '<' in the overlap condition

Step-by-Step Solution

Step 1: Understand overlap condition
Intervals that start exactly at last_end do not overlap and should be allowed.
Step 2: Identify incorrect operator
Using '<=' causes intervals starting exactly at last_end to be considered overlapping, reducing count incorrectly.
Final Answer:
Option D -> Option D
Quick Check:
Change '<=' to '<' fixes the bug [OK]

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

Common Mistakes:

MISTAKES

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

Trap Explanation:

PITFALL

Inclusive overlap check looks safer but wrongly excludes valid intervals starting at last_end.

Interviewer Note:

CONTEXT

Tests attention to boundary conditions in greedy interval selection.

Master "Non-overlapping Intervals (Max Non-Overlap)" in Intervals

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Intervals Quizzes

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?

Step 1: Understand overlap condition

Step 2: Identify incorrect operator

Final Answer:

Quick Check:

Want More Practice?