Bird
Raised Fist0
Interview PrepintervalsmediumAmazonGoogle

Count of Intervals Containing Each Point

Choose your preparation mode4 modes available
📋
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
}
0/9
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
t1_01basic
Input{"intervals":[[1,4],[2,5],[7,9]],"points":[2,5,8]}
Expected[2,1,1]

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.

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

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.

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

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

t2_02edge
Input{"intervals":[[5,5]],"points":[5]}
Expected[1]

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

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

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

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

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

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

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

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

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

t4_01performance
Input{"_description":"n=100000 at constraint boundary - executor generates this input"}
⏱ 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.

Practice

(1/5)
1. You are given a list of meeting time intervals represented as pairs of start and end times. You need to determine if a single person can attend all meetings without any overlaps. Which approach guarantees an optimal and efficient solution?
easy
A. Use dynamic programming to find the maximum number of non-overlapping intervals.
B. Sort intervals by start time and check for any overlap by comparing each interval's start with the previous interval's end.
C. Use a brute force nested loop to compare every pair of intervals for overlap.
D. Sort intervals by end time and greedily select intervals that finish earliest to maximize the number of meetings attended.

Solution

  1. Step 1: Understand the problem requirement

    The problem asks if a single person can attend all meetings without overlap, so we must check if any intervals overlap.
  2. Step 2: Identify the correct approach

    Sorting intervals by start time and checking if any interval starts before the previous one ends guarantees detection of overlaps efficiently.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sorting by start time and checking overlaps is the standard approach [OK]
Hint: Sort by start time and check overlaps [OK]
Common Mistakes:
  • Confusing sorting by end time with start time for overlap detection
2. You are given a set of intervals representing horizontal balloons on a number line. Each balloon can be burst by shooting an arrow vertically through any point covered by the balloon's interval. What is the most efficient approach to find the minimum number of arrows needed to burst all balloons?
easy
A. Sort intervals by their end coordinate and greedily shoot arrows at the earliest possible end to cover maximum balloons.
B. Sort intervals by their start coordinate and greedily shoot arrows at the start of each balloon.
C. Use dynamic programming to find the maximum number of overlapping intervals and subtract from total balloons.
D. Use a brute force nested loop to check all pairs of intervals for overlaps and count arrows accordingly.

Solution

  1. Step 1: Understand the problem constraints

    The problem requires minimizing arrows to burst all balloons, which translates to covering intervals with minimum points.
  2. Step 2: Identify the optimal greedy strategy

    Sorting by end coordinate allows shooting an arrow at the earliest finishing balloon's end, covering all overlapping balloons starting before that point.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Sorting by end coordinate ensures minimal arrows by maximizing coverage [OK]
Hint: Sort intervals by end to greedily cover overlaps [OK]
Common Mistakes:
  • Sorting by start coordinate and shooting at start misses optimal overlaps
  • Using DP unnecessarily complicates the problem
  • Brute force is too slow for large inputs
3. Consider the following Python function that finds the minimum number of arrows to burst balloons represented as intervals. Given the input points = [[10,16],[2,8],[1,6],[7,12]], what is the value of arrows after processing all intervals?
easy
A. 1
B. 4
C. 3
D. 2

Solution

  1. Step 1: Sort intervals by end coordinate

    Sorted points: [[1,6],[2,8],[7,12],[10,16]]
  2. Step 2: Iterate and count arrows

    Start with arrow_pos=6, arrows=1. Next interval start=2 ≤ 6 (covered), next start=7 > 6 (new arrow), arrows=2, arrow_pos=12. Next start=10 ≤ 12 (covered).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Two arrows suffice to burst all balloons [OK]
Hint: Sort by end, count arrows when start > current arrow position [OK]
Common Mistakes:
  • Not sorting intervals before processing
  • Using start >= arrow_pos instead of start > arrow_pos
  • Off-by-one errors in counting arrows
4. What is the time complexity of the sweep line algorithm for finding the minimum number of platforms required given n trains, and why?
medium
A. O(n log n) due to sorting arrivals and departures separately and merging them.
B. O(n^2) because each event is compared with all others to count overlaps.
C. O(n) because we only iterate through arrivals and departures once.
D. O(n log n) because events are sorted and then processed in a single pass.

Solution

  1. Step 1: Identify sorting as the main cost

    We create 2n events and sort them by time, which takes O(n log n).
  2. Step 2: Single pass processing after sorting

    After sorting, we iterate through events once, O(n), updating counts.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Sorting dominates, linear sweep after [OK]
Hint: Sorting events dominates time complexity [OK]
Common Mistakes:
  • Assuming O(n) because of single pass ignoring sorting
  • Confusing nested loops brute force with sweep line
  • Thinking sorting arrivals and departures separately is enough
5. Suppose balloons can be reused multiple times after bursting (i.e., an arrow can burst a balloon multiple times if shot at different points). How does this affect the algorithm to find the minimum number of arrows needed?
hard
A. The original greedy algorithm still applies without changes.
B. We must use dynamic programming to track multiple bursts per balloon.
C. The problem reduces to counting unique balloons since reuse removes overlap constraints.
D. We can shoot arrows only at balloon start points to minimize arrows.

Solution

  1. Step 1: Understand reuse effect

    If balloons can be burst multiple times independently, overlapping intervals no longer reduce arrow count.
  2. Step 2: Simplify problem

    Each balloon requires at least one arrow, so minimum arrows equal number of unique balloons.
  3. Step 3: Algorithm implication

    Overlap and interval sorting become irrelevant; counting balloons suffices.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Reuse breaks overlap optimization, so count balloons directly [OK]
Hint: Reuse removes overlap benefit; count balloons directly [OK]
Common Mistakes:
  • Assuming greedy still works unchanged
  • Trying to track multiple bursts with DP unnecessarily
  • Ignoring that reuse breaks interval overlap logic
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard