Bird
Raised Fist0

Which line contains a subtle bug that causes incorrect results on some inputs?

medium🐞 Bug Identification Q7 of Q15
Intervals - Non-overlapping Intervals (Max Non-Overlap)
The following code attempts to find the maximum number of non-overlapping intervals. Which line contains a subtle bug that causes incorrect results on some inputs? ```python 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 ```
ASorting intervals by start time instead of end time
BUsing '<' instead of '<=' in the overlap check
CUpdating last_end to min(last_end, intervals[i][1]) inside the if block
DInitializing removals to 0 instead of 1
Step-by-Step Solution
Solution:
  1. Step 1: Analyze sorting key

    Sorting by start time can cause suboptimal interval selection, missing maximum count.
  2. Step 2: Understand greedy correctness

    Optimal greedy requires sorting by end time to pick earliest finishing intervals.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Sorting by start time leads to incorrect results [OK]
Quick Trick: Sort by end time, not start time [OK]
Common Mistakes:
MISTAKES
  • Sorting by start time
  • Incorrect overlap condition
  • Wrong last_end updates
Trap Explanation:
PITFALL
  • Sorting by start time looks plausible but breaks optimality on some inputs.
Interviewer Note:
CONTEXT
  • Tests ability to spot subtle greedy algorithm bugs.
Master "Non-overlapping Intervals (Max Non-Overlap)" in Intervals

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Intervals Quizzes