💡 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.
Step 1/10
·Active fill★Answer cell
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/5)
1. Consider the following code snippet implementing the sweep line approach for Employee Free Time. Given the input schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]], what is the final returned list of free time intervals?
easy
A. [[3,4],[6,10]]
B. [[3,4]]
C. [[3,4],[6,7]]
D. [[3,4],[6,10]]
Solution
Step 1: Sort events and track active intervals
Events: (1,1),(1,1),(2,-1),(3,-1),(4,1),(5,1),(6,-1),(10,-1). Active counts track busy employees.
Step 2: Identify free intervals when active==0 between events
Free time occurs between 3 and 4 only, as after 4 active increments again until 10.
Final Answer:
Option B -> Option B
Quick Check:
Only [3,4] is free time interval [OK]
Hint: Free time only when no active intervals between events [OK]
Common Mistakes:
Including intervals after 6 incorrectly as free time
2. Consider the following Python function for interval intersections:
from typing import List
def intervalIntersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
i, j = 0, 0
result = []
while i < len(A) and j < len(B):
if A[i][1] < B[j][0]:
i += 1
elif B[j][1] < A[i][0]:
j += 1
else:
start = max(A[i][0], B[j][0])
end = min(A[i][1], B[j][1])
result.append([start, end])
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return result
A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]
print(intervalIntersection(A, B))
What is the final output printed by this code?
easy
A. [[1,2],[5,5],[8,10],[15,23],[24,25],[25,26]]
B. [[1,2],[5,5],[8,10],[15,23],[24,25],[25,25]]
C. [[1,2],[5,5],[8,10],[15,23],[24,24],[25,26]]
D. [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Solution
Step 1: Trace first intersection
Compare [0,2] and [1,5]: overlap is [1,2], add to result.
Step 2: Advance pointers and find all intersections
Following pointer moves and overlaps yield [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].
Hint: Trace pointer increments carefully to avoid off-by-one errors [OK]
Common Mistakes:
Including intervals beyond intersection
Merging adjacent but non-overlapping intervals
Off-by-one in pointer increments
3. What is the time complexity of the optimal in-place merge intervals algorithm that first sorts the intervals and then merges them in one pass?
medium
A. O(n log n) due to the sorting step dominating the runtime
B. O(n) because merging is done in a single pass
C. O(n²) because each interval is compared with all others during merging
D. O(n log n) because merging requires binary searches for overlaps
Solution
Step 1: Identify the sorting step complexity.
Sorting n intervals by start time takes O(n log n) time.
Step 2: Analyze the merging step complexity.
Merging intervals in one pass is O(n), which is dominated by sorting.
Final Answer:
Option A -> Option A
Quick Check:
Sorting dominates overall complexity, merging is linear. [OK]
Hint: Sorting dominates, merging is linear [OK]
Common Mistakes:
Ignoring sorting cost
Assuming nested comparisons cause O(n²)
4. The following code attempts to merge intervals in-place after sorting. Identify the line that contains a subtle bug causing incorrect results on some inputs.
medium
A. Line 3: intervals.sort(key=lambda x: x[0])
B. Line 9: intervals[index][1] = max(intervals[index][1], intervals[i][1])
C. Line 12: return intervals # missing slicing after in-place merge
D. Line 8: if intervals[i][0] <= intervals[index][1]:
Solution
Step 1: Understand the in-place merge modifies intervals up to index.
After merging, only intervals[:index+1] are valid merged intervals.
Step 2: Identify the bug in the return statement.
Returning the entire intervals list without slicing includes extra unmerged intervals, causing incorrect output.
Final Answer:
Option C -> Option C
Quick Check:
Return intervals[:index+1] to exclude leftover intervals. [OK]
Hint: Return sliced intervals after in-place merge [OK]
Common Mistakes:
Forgetting to slice after in-place merge
Modifying list while iterating without adjusting index
5. Suppose meetings can be scheduled with negative start or end times (e.g., representing times before a reference point). Which modification to the min-heap approach is necessary to correctly compute the minimum number of meeting rooms?
hard
A. Adjust the comparison in the heap to handle negative end times by using a max-heap instead of min-heap.
B. Sort intervals by absolute value of start times to handle negative values correctly.
C. Sort intervals normally by start time and use the min-heap approach as usual; negative times do not affect logic.
D. No modification needed; the existing min-heap approach works regardless of negative times.
Solution
Step 1: Understand sorting by start time works with negative values.
Sorting by start time orders intervals correctly even if times are negative.
Step 2: Confirm min-heap logic remains valid.
Heap tracks earliest end time; negative values do not affect min-heap property or comparison logic.
Step 3: No need for absolute value sorting or max-heap.
Using absolute values or max-heap breaks the logic of interval ordering and room reuse.
Final Answer:
Option C -> Option C
Quick Check:
Negative times do not change sorting or heap logic [OK]
Hint: Sorting by start time works even with negative times [OK]
Common Mistakes:
Sorting by absolute values breaks interval order
Switching to max-heap unnecessarily
Assuming negative times require special handling
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.