Count of Intervals Containing Each Point

▶

Steps

setup

Create events for interval starts

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.

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. 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

1. 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.

2. 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.

3. Final Answer:

   Option B -> Option B

4. 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. What is the time complexity of the optimal algorithm that determines if a person can attend all meetings given n intervals, where the algorithm sorts intervals by start time and then checks for overlaps in a single pass?

medium

A. O(n) because we only scan the intervals once after sorting

B. O(n^2) because each interval is compared with all others for overlaps

C. O(n log n) due to sorting the intervals by start time

D. O(log n) because sorting can be done in logarithmic time

Solution

1. Step 1: Identify sorting cost

   Sorting n intervals by start time takes O(n log n) time.

2. Step 2: Identify overlap check cost

   Single pass to check overlaps is O(n), which is dominated by sorting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting dominates total time complexity [OK]

Hint: Sorting dominates complexity -> O(n log n) [OK]

Common Mistakes:

• Confusing single pass check as O(n log n)
• Assuming nested loops cause O(n^2) here

3. Suppose the meeting intervals can be reused multiple times (i.e., a meeting can be attended multiple times if no overlaps occur). Which modification to the algorithm is necessary to correctly determine if a person can attend all meetings without overlap?

hard

A. Sort intervals by end time and greedily select intervals to maximize non-overlapping meetings.

B. No change needed; the original algorithm already handles reuse correctly.

C. Use a frequency map to count how many times each interval appears and check overlaps accordingly.

D. Sort intervals by start time and check overlaps as before, but also track counts of repeated intervals.

Solution

1. Step 1: Understand reuse scenario

   Reusing intervals means attending multiple instances of the same meeting, so we want to maximize the number of non-overlapping meetings.

2. Step 2: Identify correct approach

   Sorting by end time and greedily selecting earliest finishing meetings maximizes non-overlapping intervals, handling reuse correctly.

3. Step 3: Why other options fail

   Original algorithm only checks if all intervals can be attended once; frequency maps or tracking counts do not solve scheduling conflicts optimally.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Greedy by end time is classic interval scheduling for maximum non-overlapping intervals [OK]

Hint: Reuse requires interval scheduling by end time [OK]

Common Mistakes:

• Assuming original overlap check suffices for reuse
• Trying to track counts without scheduling logic

4. Suppose intervals can be reused multiple times (i.e., you can merge overlapping intervals repeatedly, possibly reusing intervals). Which modification to the merge intervals algorithm correctly handles this scenario?

hard

A. Use the same sorting + one pass merge approach; repeated intervals will be merged naturally.

B. Sort intervals and repeatedly apply the merge pass until no changes occur, which may take multiple passes.

C. Use a brute force nested loop approach to merge intervals until no overlaps remain.

D. Use a graph-based approach to find connected components of overlapping intervals and merge each component.

Solution

1. Step 1: Understand that reusing intervals means overlaps can form complex connected groups.

   Simple one-pass merge assumes intervals appear once and sorted order suffices.

2. Step 2: Recognize that overlapping intervals form connected components in a graph.

   Building a graph where intervals are nodes and edges represent overlaps allows merging all connected intervals correctly.

3. Step 3: Evaluate options.

   Use the same sorting + one pass merge approach; repeated intervals will be merged naturally. fails because one pass merge assumes no reuse. Sort intervals and repeatedly apply the merge pass until no changes occur, which may take multiple passes. is inefficient and may not terminate quickly. Use a brute force nested loop approach to merge intervals until no overlaps remain. is brute force and inefficient. Use a graph-based approach to find connected components of overlapping intervals and merge each component. correctly models the problem and merges all connected intervals.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Graph connected components capture all overlapping intervals including reuse. [OK]

Hint: Model reuse as graph connected components [OK]

Common Mistakes:

• Assuming one pass merge works with reuse
• Using repeated merges without termination guarantee

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

1. 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.

2. Step 2: Maintain departure-before-arrival ordering on tie to avoid overcounting

   This ordering is critical regardless of time values or multiple arrivals/departures.

3. Step 3: Continue using sweep line approach for efficiency and correctness

   Nested loops or DP are inefficient or unnecessary for this variant.

4. Final Answer:

   Option A -> Option A

5. 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