Count of Intervals Containing Each Point

📋

Problem

Imagine you are organizing multiple events throughout a day and want to know how many events are happening simultaneously at specific times.

Given a list of intervals and a list of points, determine for each point how many intervals contain it. An interval [start, end] contains a point p if start ≤ p ≤ end. Input: - intervals: List of n intervals, each interval is a pair of integers [start, end]. - points: List of m integers representing points. Output: - List of integers where the ith element is the count of intervals containing points[i].

1 ≤ n, m ≤ 10^5-10^9 ≤ start ≤ end ≤ 10^9-10^9 ≤ points[i] ≤ 10^9

Edge cases: No intervals and some points → all counts zeroIntervals with zero length (start == end) and points exactly at that position → count should include those pointsPoints outside all intervals → counts zero

</>

IDE

def count_intervals_brute(intervals: list[list[int]], points: list[int]) -> list[int]:public int[] countIntervalsBrute(int[][] intervals, int[] points)vector<int> countIntervalsBrute(vector<vector<int>> intervals, vector<int> points)function countIntervalsBrute(intervals, points)

def count_intervals_brute(intervals, points):
    # Write your solution here
    pass

class Solution {
    public int[] countIntervalsBrute(int[][] intervals, int[] points) {
        // Write your solution here
        return new int[points.length];
    }
}

#include <vector>
using namespace std;

vector<int> countIntervalsBrute(vector<vector<int>> intervals, vector<int> points) {
    // Write your solution here
    return vector<int>(points.size(), 0);
}

function countIntervalsBrute(intervals, points) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1,0,1]Failing to count all intervals containing a point; possibly stopping after first match.✅ Remove early breaks in loops; count all intervals where start <= point <= end.

Wrong: [0,0,0]Using strict inequalities (start < point < end) excluding points on boundaries.✅ Change condition to inclusive: start <= point <= end.

Wrong: [0,1,0]Not handling zero-length intervals correctly; points equal to start and end not counted.✅ Include equality in interval containment check for zero-length intervals.

Wrong: [0,0,0]Code crashes or returns zeros when intervals list is empty due to missing empty check.✅ Add check for empty intervals list and return zero counts for all points.

Wrong: Timeout or no outputUsing brute force O(n*m) approach on large inputs causing TLE.✅ Implement sorting and line sweep or binary search approach to reduce complexity to O((n+m)log(n+m)).

✓

Test Cases

Focus on handling empty intervals and points at exact boundaries correctly.

Watch out for off-by-one errors and greedy counting mistakes.

Think about how to reduce complexity from O(n*m) to O((n+m)log(n+m)) using sorting and line sweep.

t1_01basic

Input{"intervals":[[1,4],[2,5],[7,9]],"points":[2,5,8]}

Expected[2,1,1]

⏱ Performance - must finish in 2000ms

Point 2 is inside intervals [1,4] and [2,5], count 2; point 5 inside [2,5], count 1; point 8 inside [7,9], count 1.

💡 Consider checking each point against all intervals.

💡 Brute force: for each point, count intervals where start <= point <= end.

💡 Implement nested loops: outer over points, inner over intervals, increment count if condition holds.

Why it failed: Incorrect counts indicate failure to check all intervals for each point or wrong interval containment condition. Fix by ensuring start <= point <= end is checked for every interval.

✓ Correct counts confirm proper interval containment checks for all points.

t1_02basic

Input{"intervals":[[0,0],[1,2],[3,4]],"points":[0,1,3,5]}

Expected[1,1,1,0]

⏱ Performance - must finish in 2000ms

Point 0 inside [0,0], count 1; point 1 inside [1,2], count 1; point 3 inside [3,4], count 1; point 5 outside all intervals, count 0.

💡 Check points exactly at interval boundaries.

💡 Intervals with zero length count if point equals start and end.

💡 Ensure condition start <= point <= end includes equality for zero-length intervals.

Why it failed: Failing to include points equal to interval boundaries causes undercount. Fix by using <= and >= in containment check.

✓ Correctly counting boundary points confirms inclusive interval checks.

t2_01edge

Input{"intervals":[],"points":[1,2,3]}

Expected[0,0,0]

⏱ Performance - must finish in 2000ms

No intervals means no points are contained; all counts zero.

💡 What if there are no intervals at all?

💡 Check if your code handles empty intervals list without errors.

💡 Return zero counts for all points when intervals list is empty.

Why it failed: Code crashes or returns non-zero counts when intervals list is empty. Fix by adding a check for empty intervals and returning zeros accordingly.

✓ Proper handling of empty intervals returns zero counts for all points.

t2_02edge

Input{"intervals":[[5,5]],"points":[5]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single zero-length interval [5,5] contains point 5 exactly, count 1.

💡 Test intervals where start equals end.

💡 Points exactly equal to start/end should be counted.

💡 Ensure condition uses <= and >= to include zero-length intervals.

Why it failed: Failing to count points equal to zero-length interval boundaries causes zero count. Fix by using inclusive comparisons.

✓ Correctly counting zero-length intervals confirms inclusive boundary checks.

t2_03edge

Input{"intervals":[[1,3],[2,4],[3,5]],"points":[3]}

Expected[3]

⏱ Performance - must finish in 2000ms

All intervals overlap at point 3, so count is 3.

💡 Check points where multiple intervals overlap.

💡 Count all intervals containing the point, not just one.

💡 Sum counts for all intervals where start <= point <= end.

Why it failed: Counting only one interval per point or stopping early causes undercount. Fix by checking all intervals for each point.

✓ Correctly counting overlapping intervals confirms full iteration over intervals.

t3_01corner

Input{"intervals":[[1,2],[3,4],[5,6]],"points":[2,3,4]}

Expected[1,1,1]

⏱ Performance - must finish in 2000ms

Points at interval boundaries counted correctly: 2 in [1,2], 3 and 4 in [3,4].

💡 Beware off-by-one errors at interval boundaries.

💡 Check if your code uses < or <= in comparisons.

💡 Use inclusive checks: start <= point <= end to fix off-by-one errors.

Why it failed: Using strict inequalities excludes boundary points causing undercount. Fix by changing < and > to <= and >= in interval checks.

✓ Inclusive boundary checks correctly count points on interval edges.

t3_02corner

Input{"intervals":[[1,5]],"points":[0,1,5,6]}

Expected[0,1,1,0]

⏱ Performance - must finish in 2000ms

Points outside interval [1,5] get zero; points at boundaries counted once.

💡 Test points outside all intervals.

💡 Ensure no false positives for points less than start or greater than end.

💡 Check condition start <= point <= end strictly.

Why it failed: Counting points outside intervals indicates incorrect condition. Fix by enforcing start <= point <= end strictly.

✓ Correctly excluding points outside intervals confirms proper boundary checks.

t3_03corner

Input{"intervals":[[1,3],[2,4],[3,5]],"points":[3]}

Expected[3]

⏱ Performance - must finish in 2000ms

Greedy approach that stops after first match fails; all intervals containing point 3 must be counted.

💡 Beware greedy approaches that stop counting after first interval found.

💡 Count all intervals containing each point, not just one.

💡 Use full iteration over intervals for each point to fix greedy trap.

Why it failed: Greedy early exit causes undercount of intervals containing point. Fix by removing early breaks and counting all intervals.

✓ Full iteration ensures all intervals containing point are counted.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000 intervals and points at constraint boundary; O(n*m) brute force will TLE; efficient O((n+m)log(n+m)) needed.

💡 Brute force O(n*m) is too slow for large inputs.

💡 Use sorting and line sweep or binary search to optimize.

💡 Implement event-based line sweep counting intervals efficiently.

Why it failed: Brute force approach causes TLE due to O(n*m) complexity. Fix by implementing line sweep or binary search approach with O((n+m)log(n+m)) complexity.

✓ Efficient algorithm passes within time limit confirming correct complexity.

Practice

1. You are given a list of trips, each with a number of passengers, a start location, and an end location. You need to determine if a vehicle with a fixed capacity can carry all passengers without exceeding capacity at any point along the route. Which algorithmic approach best guarantees an optimal and efficient solution?

easy

A. Brute force simulation by incrementing passenger count at every location for each trip

B. Greedy algorithm that picks trips with earliest end location first

C. Dynamic programming to find maximum passengers at each location using state transitions

D. Sweep line algorithm that processes passenger count changes at trip start and end points

Solution

1. Step 1: Understand problem constraints

   The problem requires tracking passenger counts over intervals defined by start and end locations.

2. Step 2: Identify suitable algorithm

   Sweep line processes events (passenger changes) in sorted order, efficiently tracking capacity usage without simulating every location.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sweep line handles interval events optimally [OK]

Hint: Intervals with start/end events -> sweep line [OK]

Common Mistakes:

• Assuming greedy earliest end works for capacity constraints
• Thinking DP is needed for counting passengers
• Using brute force for large location ranges

2. Given multiple employees' schedules with intervals representing their busy times, which algorithmic approach guarantees finding all common free time intervals where no employee is busy?

easy

A. Greedy interval scheduling that picks earliest finishing intervals

B. Dynamic programming to find maximum non-overlapping intervals

C. Sweep line / event processing that tracks interval start and end events

D. Brute force checking every time point across all intervals

Solution

1. Step 1: Understand problem requires identifying gaps where no intervals overlap

   Greedy scheduling or DP focus on selecting intervals, not gaps between them.

2. Step 2: Sweep line processes all start/end events in order, tracking active intervals to find free gaps

   This approach efficiently detects when no employee is busy, yielding correct free times.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sweep line tracks active intervals and finds free gaps [OK]

Hint: Sweep line tracks interval endpoints to find free gaps [OK]

Common Mistakes:

• Assuming greedy or DP can find free gaps directly

3. Examine the following buggy code for interval intersections:

def intervalIntersection(A, B):
    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

What is the bug in this code?

medium

A. The condition 'if A[i][1] <= B[j][0]' should use '<' instead of '<=' to correctly detect touching intervals.

B. The pointer increments inside the else block are reversed; they should increment the pointer with the larger endpoint.

C. The overlap condition should check 'start < end' instead of 'start <= end' to avoid zero-length intervals.

D. The code does not handle empty input lists, which can cause runtime errors.

Solution

1. Step 1: Analyze overlap condition

   Using '<=' excludes intervals that touch at a point (e.g., end == start), missing valid intersections.

2. Step 2: Correct condition

   Changing to '<' ensures intervals that share a boundary point are considered intersecting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inclusive endpoints require '<' not '<=' to detect touching intervals [OK]

Hint: Check boundary conditions carefully for inclusive intervals [OK]

Common Mistakes:

• Using <= instead of <
• Reversing pointer increments
• Ignoring empty inputs

4. If employees can have intervals with negative start or end times (e.g., [-5, 0]) or zero-length intervals, which modification to the sweep line algorithm is necessary to correctly find free time?

hard

A. Ignore zero-length intervals and ensure sorting places end events before start events at ties

B. Treat zero-length intervals as free time intervals

C. Sort events only by time, ignoring event type

D. Merge touching intervals as free time gaps

Solution

1. Step 1: Handle zero-length intervals

   Zero-length intervals like [2,2] do not represent busy time and should be ignored to avoid false free intervals.

2. Step 2: Maintain correct sorting order

   Sorting end events before start events at same time prevents reporting free time between touching intervals or zero-length intervals.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ignoring zero-length intervals and correct sorting avoids invalid free times [OK]

Hint: Ignore zero-length intervals and sort end before start events [OK]

Common Mistakes:

• Counting zero-length intervals as free time
• Sorting start before end events

5. Suppose the intervals list can contain overlapping intervals initially (not guaranteed sorted or disjoint), and you want to insert a new interval and return the merged list. Which modification to the optimal approach is necessary to handle this variant correctly?

hard

A. Insert the new interval in the correct position without sorting, then merge only intervals overlapping with the new interval.

B. Append the new interval, then sort and merge all intervals including the original overlapping ones.

C. Skip sorting and merge intervals only if they overlap with the new interval to improve efficiency.

D. Use a balanced tree data structure to insert and merge intervals dynamically without sorting.

Solution

1. Step 1: Understand initial intervals may overlap

   Since intervals are not guaranteed sorted or disjoint, merging must consider all intervals, not just those overlapping newInterval.

2. Step 2: Modify approach to handle all overlaps

   Appending newInterval and sorting all intervals ensures correct order, then merging all intervals handles existing overlaps and new overlaps caused by insertion.

3. Step 3: Why other options fail

   Options B and C assume partial merging which misses existing overlaps; D is overcomplicated and not required.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Sorting and merging all intervals handles arbitrary overlaps [OK]

Hint: Sort and merge all intervals when initial list may overlap [OK]

Common Mistakes:

• Assuming initial intervals are sorted and disjoint
• Trying partial merges only around new interval
• Skipping sorting leads to incorrect merges