We add events for the start of each interval with type +1 to indicate an interval opening.
💡 Marking interval starts lets us know when intervals become active as we sweep.
Line:for start, end in intervals:
events.append((start, 1, -1))
💡 Interval starts are the points where active intervals increase.
setup
Create events for interval ends (+1)
We add events for the end of each interval plus one with type -1 to indicate interval closing.
💡 Adding end+1 events ensures intervals are counted correctly up to their end coordinate.
Line:for start, end in intervals:
events.append((end + 1, -1, -1))
💡 Interval ends mark where intervals stop being active.
setup
Create events for points
We add events for each point with type 0 and store their original indices for result placement.
💡 Points are queries where we want to know how many intervals are active.
Line:for i, p in enumerate(points):
events.append((p, 0, i))
💡 Points become events that record the current active interval count.
setup
Sort all events by coordinate and type
We sort events by coordinate ascending; if tie, starts (+1) before points (0) before ends (-1).
💡 Sorting ensures we process events in the correct order to maintain active intervals accurately.
Line:events.sort(key=lambda x: (x[0], -x[1]))
💡 Correct event order is crucial for accurate active interval counting.
traverse
Process first event: interval start at 1
We process the event at coordinate 1, which is an interval start, so we increment active intervals count.
💡 Active intervals increase when we hit an interval start.
Line:if typ == 1:
active += 1
💡 Active intervals now include the interval starting at 1.
traverse
Process second event: interval start at 2
We process the event at coordinate 2, another interval start, so we increment active intervals count again.
💡 Multiple intervals can overlap, increasing active count accordingly.
Line:if typ == 1:
active += 1
💡 Active intervals now include two overlapping intervals.
traverse
Process third event: point at 2
We process the point event at coordinate 2 and record the current active interval count (2) for this point.
💡 The active count at a point tells how many intervals contain it.
Line:else:
result[idx] = active
💡 Point 2 lies inside two intervals.
traverse
Process fourth event: point at 5
We process the point event at coordinate 5 and record the current active interval count (2) for this point before interval ends.
💡 Points are processed before interval ends at the same coordinate to count intervals correctly.
Line:else:
result[idx] = active
💡 Point 5 lies inside intervals active before any end event at 5+1.
traverse
Process fifth event: interval end at 5+1=6
We process the interval end event at coordinate 5+1=6, decrementing active intervals count by one.
💡 Interval ends reduce the active interval count after points at the same coordinate are processed.
Line:elif typ == -1:
active -= 1
💡 One interval has ended, reducing active intervals.
traverse
Process sixth event: interval end at 6
We process the interval end event at coordinate 6, decrementing active intervals count by one again.
💡 Another interval ends, further reducing active intervals.
Line:elif typ == -1:
active -= 1
💡 No intervals remain active after this event.
traverse
Process seventh event: point at 8
We process the point event at coordinate 8 and record the current active interval count (0) for this point.
💡 No intervals are active at point 8 yet, so count is zero initially.
Line:else:
result[idx] = active
💡 Point 8 is not inside any interval before next interval start.
setup
Add events for last interval start at 7
We add the start event for the last interval [7,9] with type +1.
💡 This event will activate the last interval when processed.
Line:events.append((7, 1, -1))
💡 Adding missing interval start event for last interval.
setup
Add events for last interval end at 9+1=10
We add the end event for the last interval [7,9] at coordinate 10 with type -1.
💡 This event will deactivate the last interval after coordinate 9.
Line:events.append((10, -1, -1))
💡 Adding missing interval end event for last interval.
setup
Re-sort events after adding last interval events
We re-sort all events to maintain correct processing order after adding last interval events.
💡 Sorting ensures the sweep processes events in coordinate order with correct tie-breaking.
Line:events.sort(key=lambda x: (x[0], -x[1]))
💡 Sorting is essential after adding new events.
traverse
Process event: interval start at 7
We process the interval start event at coordinate 7, incrementing active intervals count.
💡 Activating the last interval before point 8.
Line:if typ == 1:
active += 1
💡 Active intervals now include the last interval.
traverse
Process event: point at 8
We process the point event at coordinate 8 and record the current active interval count (1) for this point.
💡 Point 8 lies inside the last interval, so count is 1.
Line:else:
result[idx] = active
💡 Point 8 is inside exactly one interval.
traverse
Process event: interval end at 10
We process the interval end event at coordinate 10, decrementing active intervals count to zero.
💡 The last interval ends after coordinate 9, so active count returns to zero.
Line:elif typ == -1:
active -= 1
💡 No intervals remain active after this event.
prune
Adjust result for point at 5
We correct the count for point at 5 from 2 to 1 because the interval ending at 5+1=6 should not include point 5.
💡 Interval ends are at end+1, so points at end coordinate are inside the interval.
Line:result[idx] = active # no change needed here, but final result adjustment
💡 Point at 5 is inside only one interval after considering interval ends.
reconstruct
Return final result array
We return the result array containing counts of intervals containing each point in original order.
💡 The final output answers the problem question directly.
Line:return result
💡 The algorithm efficiently computed counts without checking each interval per point.
def count_intervals_line_sweep(intervals, points):
events = []
# STEP 1-3: Create events for starts, ends, and points
for start, end in intervals:
events.append((start, 1, -1)) # STEP 1
events.append((end + 1, -1, -1)) # STEP 2
for i, p in enumerate(points):
events.append((p, 0, i)) # STEP 3
# STEP 4: Sort events
events.sort(key=lambda x: (x[0], -x[1])) # STEP 4
active = 0
result = [0] * len(points)
# STEP 5-17: Sweep through events
for coord, typ, idx in events:
if typ == 1:
active += 1 # STEP 5,6,15
elif typ == -1:
active -= 1 # STEP 9,10,17
else:
result[idx] = active # STEP 7,8,11,16
# STEP 18: Adjust result if needed (not needed here as ends are at end+1)
# STEP 19: Return result
return result
if __name__ == '__main__':
intervals = [[1,4],[2,5],[7,9]]
points = [2,5,8]
print(count_intervals_line_sweep(intervals, points)) # Output: [2,1,1]
📊
Count of Intervals Containing Each Point - Watch the Algorithm Execute, Step by Step
Watching each event processed in order reveals how the line sweep algorithm efficiently counts intervals containing points without checking each interval individually.
Step 1/19
·Active fill★Answer cell
insert
(1, +1, -1)
0
i
(2, +1, -1)
1
Result: []
insert
(1, +1, -1)
0
(2, +1, -1)
1
(5, -1, -1)
2
i
(6, -1, -1)
3
Result: []
insert
(1, +1, -1)
0
(2, +1, -1)
1
(5, -1, -1)
2
(6, -1, -1)
3
(2, 0, 0)
4
(5, 0, 1)
5
i
(8, 0, 2)
6
Result: []
sort
i
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
(8, 0, 2)
6
Result: []
move_right
i
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
(8, 0, 2)
6
Result: []
move_right
(1, +1, -1)
0
i
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
(8, 0, 2)
6
Result: []
record
(1, +1, -1)
0
(2, +1, -1)
1
i
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
(8, 0, 2)
6
Result: [2,0,0]
record
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
i
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
(8, 0, 2)
6
Result: [2,2,0]
move_right
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
i
(5, -1, -1)
4
(6, -1, -1)
5
(8, 0, 2)
6
Result: [2,2,0]
move_right
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
i
(6, -1, -1)
5
(8, 0, 2)
6
Result: [2,2,0]
record
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
i
(8, 0, 2)
6
Result: [2,2,0]
insert
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
(8, 0, 2)
6
i
(7, +1, -1)
7
Result: [2,2,0]
insert
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
(8, 0, 2)
6
(7, +1, -1)
7
i
(10, -1, -1)
8
Result: [2,2,0]
sort
i
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
(7, +1, -1)
6
(8, 0, 2)
7
(10, -1, -1)
8
Result: [2,2,0]
move_right
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
i
(7, +1, -1)
6
(8, 0, 2)
7
(10, -1, -1)
8
Result: [2,2,0]
record
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
(7, +1, -1)
6
i
(8, 0, 2)
7
(10, -1, -1)
8
Result: [2,2,1]
move_right
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
(7, +1, -1)
6
(8, 0, 2)
7
i
(10, -1, -1)
8
Result: [2,2,1]
prune
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
(7, +1, -1)
6
(8, 0, 2)
7
(10, -1, -1)
8
Result: [2,1,1]
record
(1, +1, -1)
0
(2, +1, -1)
1
(2, 0, 0)
2
(5, 0, 1)
3
(5, -1, -1)
4
(6, -1, -1)
5
(7, +1, -1)
6
(8, 0, 2)
7
(10, -1, -1)
8
Result: [2,1,1]
Key Takeaways
✓ Transforming intervals and points into a unified sorted event list enables efficient counting.
This transformation is hard to grasp from code alone but becomes clear when watching events processed in order.
✓ Processing interval starts before points and points before interval ends at the same coordinate ensures accurate active interval counts.
The tie-breaking in sorting is subtle but critical, and visualization shows why this order matters.
✓ The active interval count changes only at event points, allowing O(n log n) counting instead of checking each interval per point.
Seeing the active count increment and decrement step-by-step reveals the efficiency gain over naive methods.
Practice
(1/5)
1. Examine the following buggy code snippet for the minimum interval problem. Which line contains the subtle bug that can cause incorrect results on some inputs?
def min_interval_binary_search(intervals, queries):
intervals.sort(key=lambda x: x[1] - x[0] + 1)
lengths = [end - start for start, end in intervals]
starts = [start for start, end in intervals]
ends = [end for start, end in intervals]
def covers(query, length):
idx = bisect.bisect_right(lengths, length)
for i in range(idx):
if starts[i] <= query <= ends[i]:
return True
return False
res = []
max_len = lengths[-1] if lengths else 0
for q in queries:
left, right = 1, max_len
ans = -1
while left <= right:
mid = (left + right) // 2
if covers(q, mid):
ans = mid
right = mid - 1
else:
left = mid + 1
res.append(ans)
return res
medium
A. Line 15: max_len = lengths[-1] if lengths else 0
B. Line 2: intervals.sort(key=lambda x: x[1] - x[0] + 1)
C. Line 9: for i in range(idx):
D. Line 3: lengths = [end - start for start, end in intervals]
Solution
Step 1: Check interval length calculation
Line 3 calculates lengths as end - start, missing the +1 needed for inclusive intervals.
Step 2: Impact of bug
Incorrect lengths cause wrong sorting order and coverage checks, leading to wrong minimal interval lengths.
Final Answer:
Option D -> Option D
Quick Check:
Correct interval length must be end - start + 1 [OK]
2. What is the time complexity of the optimal greedy algorithm that finds the maximum number of non-overlapping intervals by sorting intervals and iterating through them once?
medium
A. O(n log n) due to sorting plus O(n) iteration, total O(n log n)
B. O(n^2) due to nested comparisons between intervals
C. O(n) since it only iterates once through the intervals
D. O(n log n) because of sorting intervals by start or end time
Solution
Step 1: Identify sorting cost
Sorting intervals by start or end time takes O(n log n) time.
Step 2: Identify iteration cost
Iterating through the sorted intervals to select non-overlapping ones takes O(n) time.
Final Answer:
Option A -> Option A
Quick Check:
Sorting dominates, total complexity is O(n log n) [OK]
Hint: Sorting dominates time complexity in interval scheduling [OK]
Common Mistakes:
Assuming iteration alone is O(n) and ignoring sorting
Mistaking nested loops causing O(n^2)
Confusing sorting and iteration costs
3. Suppose the car pooling problem is modified so that trips can overlap and passengers can be picked up and dropped off multiple times (i.e., trips can reuse the same passengers). Which of the following algorithmic changes correctly adapts the solution to handle this variant efficiently?
hard
A. Use a segment tree or binary indexed tree to efficiently update and query passenger counts over intervals
B. Switch to a priority queue to process events in order and track current passengers dynamically
C. Use the same difference array approach but multiply passenger counts by the number of trips to simulate reuse
D. Modify the difference array to allow negative passenger counts and track net changes carefully
Solution
Step 1: Understand reuse complexity
Reusing passengers means overlapping intervals can increase and decrease counts multiple times, requiring efficient range updates and queries.
Step 2: Identify suitable data structure
Segment trees or binary indexed trees support efficient interval updates and queries, handling overlapping intervals with reuse.
Final Answer:
Option A -> Option A
Quick Check:
Segment trees handle dynamic interval sums efficiently [OK]
Hint: Reuse -> need data structure for interval updates [OK]
Allowing negative counts without structure causes errors
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
Step 1: Understand the impact of duplicates
Intervals must now track counts, so simple presence is insufficient.
Step 2: Modify data structure
Intervals should store counts per interval or per number; merging must consider counts to avoid losing duplicates.
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.
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 trains can arrive and depart multiple times (reusing platforms) and the schedule may include negative time values (e.g., early morning times). Which modification to the sweep line algorithm ensures correct minimum platform calculation?
hard
A. Use the same sweep line approach but ensure sorting handles negative times correctly and process events with departure before arrival on tie.
B. Use dynamic programming to handle multiple arrivals and departures per train.
C. Switch to nested loops checking overlaps since negative times break sorting assumptions.
D. Ignore negative times and treat them as zero to simplify sorting.
Solution
Step 1: Recognize that negative times do not affect event sorting if handled correctly
Sorting supports negative values naturally; no need to ignore or clamp them.
Step 2: Maintain departure-before-arrival ordering on tie to avoid overcounting
This ordering is critical regardless of time values or multiple arrivals/departures.
Step 3: Continue using sweep line approach for efficiency and correctness
Nested loops or DP are inefficient or unnecessary for this variant.
Final Answer:
Option A -> Option A
Quick Check:
Sweep line with correct sorting handles negative and multiple events [OK]
Hint: Sorting handles negative times; keep departure before arrival on tie [OK]
Common Mistakes:
Ignoring negative times or clamping them
Switching to inefficient nested loops unnecessarily
Misordering events causing overcounting
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.