Count of Intervals Containing Each Point

🎯

Count of Intervals Containing Each Point

mediumINTERVALSAmazonGoogle

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

💡 This problem asks us to find how many intervals cover each given point. Beginners often struggle because they try to check each point against all intervals directly, which is inefficient. Understanding how sorting and prefix sums can optimize this is key.

📋

Problem Statement

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

💡

Example

Input"intervals = [[1,4],[2,5],[7,9]], points = [2,5,8]"

Output[2,1,1]

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

• No intervals and some points → all counts zero
• Intervals with zero length (start == end) and points exactly at that position → count should include those points
• Points outside all intervals → counts zero
• All intervals overlapping at a single point → counts equal to number of intervals at that point

⚠️

Common Mistakes

Not sorting events correctly in line sweep

Incorrect counts due to wrong processing order of starts, points, and ends

✅ Sort events by coordinate and process starts before points before ends

Using end instead of end+1 for interval end event in line sweep

Points exactly at interval end are excluded incorrectly

✅ Use end+1 for end event to ensure inclusive interval coverage

Using bisect_left instead of bisect_right for counting starts in binary search approach

Under-count intervals starting exactly at the point

✅ Use bisect_right for starts to include intervals starting at the point

Not handling empty intervals or empty points arrays

Code may crash or produce wrong output

✅ Add checks or handle empty inputs gracefully

Confusing inclusive and exclusive interval boundaries

Wrong counts for points on interval edges

✅ Clarify problem definition and implement accordingly

🧠

Brute Force (Nested Loops)

💡 This approach is the most straightforward and helps understand the problem deeply by directly checking each point against every interval, though it is inefficient for large inputs.

Intuition

For each point, check every interval to see if the point lies within it, and count how many intervals contain that point.

Algorithm

1. Initialize a result list with zeros for each point.
2. For each point, iterate over all intervals.
3. Check if the point lies within the current interval.
4. If yes, increment the count for that point.

💡 The nested loops make it easy to understand but hard to scale; beginners often miss the nested iteration structure.

</>

Code

def count_intervals_brute(intervals, points):
    result = [0] * len(points)
    for i, p in enumerate(points):
        for start, end in intervals:
            if start <= p <= end:
                result[i] += 1
    return result

# Driver code
if __name__ == '__main__':
    intervals = [[1,4],[2,5],[7,9]]
    points = [2,5,8]
    print(count_intervals_brute(intervals, points))  # Output: [2,1,1]

Line Notes

result = [0] * len(points)Initialize counts for each point to zero

for i, p in enumerate(points):Outer loop to process each point individually

for start, end in intervals:Inner loop to check all intervals for current point

if start <= p <= end:Check if point lies inside the interval

result[i] += 1Increment count if point is inside interval

import java.util.*;
public class CountIntervalsBrute {
    public static int[] countIntervalsBrute(int[][] intervals, int[] points) {
        int[] result = new int[points.length];
        for (int i = 0; i < points.length; i++) {
            int p = points[i];
            for (int[] interval : intervals) {
                if (interval[0] <= p && p <= interval[1]) {
                    result[i]++;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,4},{2,5},{7,9}};
        int[] points = {2,5,8};
        System.out.println(Arrays.toString(countIntervalsBrute(intervals, points))); // [2,1,1]
    }
}

Line Notes

int[] result = new int[points.length];Initialize result array with zero counts

for (int i = 0; i < points.length; i++) {Outer loop over each point

for (int[] interval : intervals) {Inner loop over all intervals

if (interval[0] <= p && p <= interval[1]) {Check if point lies inside interval

result[i]++;Increment count for current point

#include <iostream>
#include <vector>
using namespace std;

vector<int> countIntervalsBrute(const vector<pair<int,int>>& intervals, const vector<int>& points) {
    vector<int> result(points.size(), 0);
    for (int i = 0; i < points.size(); i++) {
        int p = points[i];
        for (auto& interval : intervals) {
            if (interval.first <= p && p <= interval.second) {
                result[i]++;
            }
        }
    }
    return result;
}

int main() {
    vector<pair<int,int>> intervals = {{1,4},{2,5},{7,9}};
    vector<int> points = {2,5,8};
    vector<int> res = countIntervalsBrute(intervals, points);
    for (int c : res) cout << c << ' ';
    cout << '\n'; // Output: 2 1 1
    return 0;
}

Line Notes

vector<int> result(points.size(), 0);Initialize counts to zero for each point

for (int i = 0; i < points.size(); i++) {Outer loop over points

for (auto& interval : intervals) {Inner loop over intervals

if (interval.first <= p && p <= interval.second) {Check if point lies inside interval

result[i]++;Increment count for point

function countIntervalsBrute(intervals, points) {
    const result = new Array(points.length).fill(0);
    for (let i = 0; i < points.length; i++) {
        const p = points[i];
        for (const [start, end] of intervals) {
            if (start <= p && p <= end) {
                result[i]++;
            }
        }
    }
    return result;
}

// Test
const intervals = [[1,4],[2,5],[7,9]];
const points = [2,5,8];
console.log(countIntervalsBrute(intervals, points)); // [2,1,1]

Line Notes

const result = new Array(points.length).fill(0);Initialize counts array with zeros

for (let i = 0; i < points.length; i++) {Outer loop over each point

for (const [start, end] of intervals) {Inner loop over intervals

if (start <= p && p <= end) {Check if point lies inside interval

result[i]++;Increment count for current point

⏱

Complexity

TimeO(n*m)

SpaceO(m)

For each of the m points, we check all n intervals, resulting in O(n*m) time. We store counts for m points.

💡 If n and m are 100,000 each, this means 10 billion operations, which is too slow for interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem and motivate optimizations.

🧠

Sorting Intervals and Points + Binary Search

💡 This approach improves efficiency by sorting intervals and points, then using binary search to count intervals covering each point.

Intuition

Sort interval starts and ends separately. For each point, count how many intervals start before or at the point and subtract how many intervals end before the point.

Algorithm

1. Extract and sort all interval start points and end points separately.
2. For each point, use binary search to find how many intervals start at or before the point.
3. Use binary search to find how many intervals end before the point.
4. The difference between these two counts is the number of intervals containing the point.

💡 The key insight is that intervals containing a point are those started but not ended before that point.

</>

Code

import bisect

def count_intervals_binary_search(intervals, points):
    starts = sorted([start for start, end in intervals])
    ends = sorted([end for start, end in intervals])
    result = []
    for p in points:
        # Count intervals started at or before p
        s_count = bisect.bisect_right(starts, p)
        # Count intervals ended before p
        e_count = bisect.bisect_left(ends, p)
        result.append(s_count - e_count)
    return result

# Driver code
if __name__ == '__main__':
    intervals = [[1,4],[2,5],[7,9]]
    points = [2,5,8]
    print(count_intervals_binary_search(intervals, points))  # Output: [2,1,1]

Line Notes

starts = sorted([start for start, end in intervals])Sort all interval start points for binary search

ends = sorted([end for start, end in intervals])Sort all interval end points for binary search

s_count = bisect.bisect_right(starts, p)Count intervals started at or before point p

e_count = bisect.bisect_left(ends, p)Count intervals ended strictly before point p

result.append(s_count - e_count)Intervals containing p are those started but not ended before p

import java.util.*;
public class CountIntervalsBinarySearch {
    public static int[] countIntervalsBinarySearch(int[][] intervals, int[] points) {
        int n = intervals.length;
        int[] starts = new int[n];
        int[] ends = new int[n];
        for (int i = 0; i < n; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int[] result = new int[points.length];
        for (int i = 0; i < points.length; i++) {
            int p = points[i];
            int sCount = upperBound(starts, p);
            int eCount = lowerBound(ends, p);
            result[i] = sCount - eCount;
        }
        return result;
    }

    private static int lowerBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    private static int upperBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] <= target) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,4},{2,5},{7,9}};
        int[] points = {2,5,8};
        System.out.println(Arrays.toString(countIntervalsBinarySearch(intervals, points))); // [2,1,1]
    }
}

Line Notes

Arrays.sort(starts);Sort interval start points for binary search

Arrays.sort(ends);Sort interval end points for binary search

int sCount = upperBound(starts, p);Count intervals started at or before point p

int eCount = lowerBound(ends, p);Count intervals ended before point p

result[i] = sCount - eCount;Calculate intervals containing point p

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lowerBound(const vector<int>& arr, int target) {
    return (int)(std::lower_bound(arr.begin(), arr.end(), target) - arr.begin());
}

int upperBound(const vector<int>& arr, int target) {
    return (int)(std::upper_bound(arr.begin(), arr.end(), target) - arr.begin());
}

vector<int> countIntervalsBinarySearch(const vector<pair<int,int>>& intervals, const vector<int>& points) {
    vector<int> starts, ends;
    for (auto& interval : intervals) {
        starts.push_back(interval.first);
        ends.push_back(interval.second);
    }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());
    vector<int> result;
    for (int p : points) {
        int sCount = upperBound(starts, p);
        int eCount = lowerBound(ends, p);
        result.push_back(sCount - eCount);
    }
    return result;
}

int main() {
    vector<pair<int,int>> intervals = {{1,4},{2,5},{7,9}};
    vector<int> points = {2,5,8};
    vector<int> res = countIntervalsBinarySearch(intervals, points);
    for (int c : res) cout << c << ' ';
    cout << '\n'; // Output: 2 1 1
    return 0;
}

Line Notes

sort(starts.begin(), starts.end());Sort interval start points for binary search

sort(ends.begin(), ends.end());Sort interval end points for binary search

int sCount = upperBound(starts, p);Count intervals started at or before point p

int eCount = lowerBound(ends, p);Count intervals ended before point p

result.push_back(sCount - eCount);Calculate intervals containing point p

function lowerBound(arr, target) {
    let left = 0, right = arr.length;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

function upperBound(arr, target) {
    let left = 0, right = arr.length;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left;
}

function countIntervalsBinarySearch(intervals, points) {
    const starts = intervals.map(i => i[0]).sort((a,b) => a-b);
    const ends = intervals.map(i => i[1]).sort((a,b) => a-b);
    const result = [];
    for (const p of points) {
        const sCount = upperBound(starts, p);
        const eCount = lowerBound(ends, p);
        result.push(sCount - eCount);
    }
    return result;
}

// Test
const intervals = [[1,4],[2,5],[7,9]];
const points = [2,5,8];
console.log(countIntervalsBinarySearch(intervals, points)); // [2,1,1]

Line Notes

const starts = intervals.map(i => i[0]).sort((a,b) => a-b);Extract and sort interval starts

const ends = intervals.map(i => i[1]).sort((a,b) => a-b);Extract and sort interval ends

const sCount = upperBound(starts, p);Count intervals started at or before point p

const eCount = lowerBound(ends, p);Count intervals ended before point p

result.push(sCount - eCount);Calculate intervals containing point p

⏱

Complexity

TimeO(n log n + m log n)

SpaceO(n + m)

Sorting intervals takes O(n log n). For each of the m points, two binary searches take O(log n), total O(m log n).

💡 For n and m = 100,000, this is about 2 million operations, which is efficient enough for interviews.

Interview Verdict: Accepted

This approach is efficient and commonly accepted in interviews for this problem size.

🧠

Line Sweep Algorithm with Events

💡 This approach uses a line sweep technique to process interval start and end points and query points in sorted order, counting active intervals efficiently.

Intuition

Create events for interval starts (+1), interval ends (-1), and points (query). Sweep through all events sorted by coordinate, updating active interval count and recording counts for points.

Algorithm

1. Create a list of events: (coordinate, type, index), where type is +1 for interval start, -1 for interval end + 1, and 0 for points.
2. Sort all events by coordinate; if tie, process starts before points before ends.
3. Initialize active interval count to zero.
4. Sweep through events: increment count on start, record count for points, decrement count on end.
5. Return recorded counts for points in original order.

💡 The event sorting and processing order ensures correct active interval counts at each point.

</>

Code

def count_intervals_line_sweep(intervals, points):
    events = []
    for start, end in intervals:
        events.append((start, 1, -1))  # interval start
        events.append((end + 1, -1, -1))  # interval end + 1
    for i, p in enumerate(points):
        events.append((p, 0, i))  # point query
    events.sort(key=lambda x: (x[0], -x[1]))  # start(+1) before point(0) before end(-1)

    active = 0
    result = [0] * len(points)
    for coord, typ, idx in events:
        if typ == 1:
            active += 1
        elif typ == -1:
            active -= 1
        else:
            result[idx] = active
    return result

# Driver code
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]

Line Notes

events.append((start, 1, -1))Mark interval start event with +1 type

events.append((end + 1, -1, -1))Mark interval end event at end+1 with -1 type to exclude end point

events.append((p, 0, i))Mark point query event with 0 type and index

events.sort(key=lambda x: (x[0], -x[1]))Sort events by coordinate; starts before points before ends

if typ == 1: active += 1Increment active intervals on start

elif typ == -1: active -= 1Decrement active intervals on end

else: result[idx] = activeRecord active intervals count for point

import java.util.*;
public class CountIntervalsLineSweep {
    static class Event implements Comparable<Event> {
        int coord, type, index;
        Event(int c, int t, int i) { coord = c; type = t; index = i; }
        public int compareTo(Event other) {
            if (this.coord != other.coord) return Integer.compare(this.coord, other.coord);
            return Integer.compare(other.type, this.type); // start(1) before point(0) before end(-1)
        }
    }

    public static int[] countIntervalsLineSweep(int[][] intervals, int[] points) {
        List<Event> events = new ArrayList<>();
        for (int[] interval : intervals) {
            events.add(new Event(interval[0], 1, -1));
            events.add(new Event(interval[1] + 1, -1, -1));
        }
        for (int i = 0; i < points.length; i++) {
            events.add(new Event(points[i], 0, i));
        }
        Collections.sort(events);

        int active = 0;
        int[] result = new int[points.length];
        for (Event e : events) {
            if (e.type == 1) active++;
            else if (e.type == -1) active--;
            else result[e.index] = active;
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,4},{2,5},{7,9}};
        int[] points = {2,5,8};
        System.out.println(Arrays.toString(countIntervalsLineSweep(intervals, points))); // [2,1,1]
    }
}

Line Notes

events.add(new Event(interval[0], 1, -1));Add interval start event with type +1

events.add(new Event(interval[1] + 1, -1, -1));Add interval end event at end+1 with type -1

events.add(new Event(points[i], 0, i));Add point query event with type 0 and index

Collections.sort(events);Sort events by coordinate and type order

if (e.type == 1) active++;Increment active intervals on start event

else if (e.type == -1) active--;Decrement active intervals on end event

else result[e.index] = active;Record active intervals count for point

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Event {
    int coord, type, index;
    Event(int c, int t, int i) : coord(c), type(t), index(i) {}
    bool operator<(const Event& other) const {
        if (coord != other.coord) return coord < other.coord;
        return type > other.type; // start(1) before point(0) before end(-1)
    }
};

vector<int> countIntervalsLineSweep(const vector<pair<int,int>>& intervals, const vector<int>& points) {
    vector<Event> events;
    for (auto& interval : intervals) {
        events.emplace_back(interval.first, 1, -1);
        events.emplace_back(interval.second + 1, -1, -1);
    }
    for (int i = 0; i < (int)points.size(); i++) {
        events.emplace_back(points[i], 0, i);
    }
    sort(events.begin(), events.end());

    int active = 0;
    vector<int> result(points.size());
    for (auto& e : events) {
        if (e.type == 1) active++;
        else if (e.type == -1) active--;
        else result[e.index] = active;
    }
    return result;
}

int main() {
    vector<pair<int,int>> intervals = {{1,4},{2,5},{7,9}};
    vector<int> points = {2,5,8};
    vector<int> res = countIntervalsLineSweep(intervals, points);
    for (int c : res) cout << c << ' ';
    cout << '\n'; // Output: 2 1 1
    return 0;
}

Line Notes

events.emplace_back(interval.first, 1, -1);Add interval start event with type +1

events.emplace_back(interval.second + 1, -1, -1);Add interval end event at end+1 with type -1

events.emplace_back(points[i], 0, i);Add point query event with type 0 and index

sort(events.begin(), events.end());Sort events by coordinate and type order

if (e.type == 1) active++;Increment active intervals on start event

else if (e.type == -1) active--;Decrement active intervals on end event

else result[e.index] = active;Record active intervals count for point

function countIntervalsLineSweep(intervals, points) {
    const events = [];
    for (const [start, end] of intervals) {
        events.push([start, 1, -1]); // interval start
        events.push([end + 1, -1, -1]); // interval end + 1
    }
    points.forEach((p, i) => events.push([p, 0, i]));
    events.sort((a, b) => a[0] - b[0] || b[1] - a[1]); // start(1) before point(0) before end(-1)

    let active = 0;
    const result = new Array(points.length).fill(0);
    for (const [coord, type, idx] of events) {
        if (type === 1) active++;
        else if (type === -1) active--;
        else result[idx] = active;
    }
    return result;
}

// Test
const intervals = [[1,4],[2,5],[7,9]];
const points = [2,5,8];
console.log(countIntervalsLineSweep(intervals, points)); // [2,1,1]

Line Notes

events.push([start, 1, -1]);Add interval start event with type +1

events.push([end + 1, -1, -1]);Add interval end event at end+1 with type -1

points.forEach((p, i) => events.push([p, 0, i]));Add point query events with type 0 and index

events.sort((a, b) => a[0] - b[0] || b[1] - a[1]);Sort events by coordinate and type order

if (type === 1) active++;Increment active intervals on start event

else if (type === -1) active--;Decrement active intervals on end event

else result[idx] = active;Record active intervals count for point

⏱

Complexity

TimeO((n + m) log (n + m))

SpaceO(n + m)

We create 2n + m events and sort them, which takes O((n + m) log (n + m)). Sweeping is O(n + m).

💡 For 100,000 intervals and points, sorting about 300,000 events is efficient and practical.

Interview Verdict: Accepted

This is the optimal approach for large inputs and is a common pattern in interval problems.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the binary search or line sweep approach is best; brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*m)	O(m)	No	N/A	Mention only - never code for large inputs
2. Sorting + Binary Search	O(n log n + m log n)	O(n + m)	No	N/A	Good balance of clarity and efficiency; safe to code
3. Line Sweep Algorithm	O((n + m) log (n + m))	O(n + m)	No	N/A	Optimal and elegant; preferred if comfortable with event sorting

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Start with the brute force approach to demonstrate understanding.Explain why brute force is inefficient and propose sorting-based improvements.Describe the binary search approach and its complexity.Finally, present the line sweep algorithm as the optimal solution.Write clean, tested code for the chosen approach.Discuss edge cases and test your code with them.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize from brute force, knowledge of sorting and binary search, and mastery of line sweep technique.

Common Follow-ups

• What if intervals are dynamic and queries come online? → Use segment trees or binary indexed trees.
• How to handle intervals with open or half-open boundaries? → Adjust event points and comparisons accordingly.

💡 These follow-ups test your ability to adapt the solution to variations and dynamic scenarios.

🔍

Pattern Recognition

When to Use

1) You have intervals and points queries; 2) Need counts of intervals covering points; 3) Large input sizes requiring efficiency; 4) Sorting or prefix sums seem applicable.

Signature Phrases

count intervals containing each pointhow many intervals cover a point

NOT This Pattern When

Problems asking for interval intersections or unions without point queries are different.

Similar Problems

Meeting Rooms II - counting overlapping intervalsEmployee Free Time - merging intervals and gaps

Practice

1. Given two lists of closed intervals, each sorted and non-overlapping within themselves, you need to find all intervals where the two lists overlap. Which approach guarantees an optimal time complexity solution?

easy

A. Use a brute force nested loop to compare every interval in the first list with every interval in the second list.

B. Use two pointers to traverse both lists simultaneously, advancing the pointer with the smaller interval endpoint to find intersections efficiently.

C. Sort all intervals from both lists together and then merge overlapping intervals to find intersections.

D. Use dynamic programming to store and compute overlapping intervals between the two lists.

Solution

1. Step 1: Understand problem constraints

   Both lists are sorted and non-overlapping internally, so a linear scan is possible.

2. Step 2: Identify the optimal approach

   Two pointers allow simultaneous traversal, comparing intervals in O(m + n) time, advancing pointers based on interval endpoints.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two pointers avoid unnecessary comparisons and achieve linear time [OK]

Hint: Two pointers exploit sorted order for linear time [OK]

Common Mistakes:

• Assuming brute force is acceptable
• Thinking sorting combined lists is needed
• Misapplying DP to interval intersection

2. You are given a list of intervals where each interval has a start and end time. Your goal is to select the maximum number of intervals such that none of the selected intervals overlap. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming that tries all subsets of intervals to find the maximum non-overlapping set.

B. Sort intervals by their start time and always pick the earliest starting interval first.

C. Sort intervals by their end time and greedily select intervals that start after the last selected interval ends.

D. Use a graph coloring algorithm to assign intervals to different colors ensuring no overlaps.

Solution

1. Step 1: Understand the problem goal

   The problem requires selecting the maximum number of intervals with no overlaps.

2. Step 2: Identify the optimal greedy strategy

   Sorting intervals by their end time and greedily picking intervals that start after the last selected interval ends ensures the maximum number of intervals are chosen.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Greedy by earliest end time is a classic optimal approach [OK]

Hint: Sort by end time for max non-overlapping intervals [OK]

Common Mistakes:

• Sorting by start time and picking earliest start first
• Trying brute force DP without pruning
• Using graph coloring which is unrelated here

3. What is the time complexity of the optimal two pointers approach for finding the intersection of two interval lists, each of length m and n respectively?

medium

A. O(max(m, n) * log(min(m, n))) due to sorting or binary search steps.

B. O(m * n), since each interval in one list is compared to all intervals in the other list.

C. O(m + n), because each pointer advances at most m or n times through the lists.

D. O(m + n + k), where k is the number of intersections found.

Solution

1. Step 1: Identify pointer movements

   Each pointer i and j moves forward only, never backward, up to m and n times respectively.

2. Step 2: Sum pointer advances

   Total steps ≤ m + n, so time complexity is O(m + n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two pointers scan each list once without nested loops [OK]

Hint: Two pointers each advance linearly, no nested iteration [OK]

Common Mistakes:

• Confusing with brute force O(m*n)
• Assuming sorting is needed
• Including output size k in complexity incorrectly

4. What is the time complexity of the optimal min-heap approach for the Meeting Rooms II problem, given n intervals? Beware of common misconceptions about sorting and heap operations.

medium

A. O(n log k) where k is the number of rooms, but k can be up to n, so effectively O(n log n).

B. O(n^2) because each interval may be compared with all others.

C. O(n log n) due to sorting and heap operations for each interval.

D. O(n) because heap operations are constant time on average.

Solution

1. Step 1: Identify sorting cost.

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

2. Step 2: Analyze heap operations.

   Each interval is pushed and possibly popped from a min-heap of size k (number of rooms). Each heap operation costs O(log k).

3. Step 3: Combine complexities.

   Total heap operations are O(n log k). Since k ≤ n, worst case is O(n log n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting + heap operations dominate; heap size bounded by n [OK]

Hint: Heap ops depend on number of rooms k, bounded by n [OK]

Common Mistakes:

• Assuming heap ops are O(1)
• Confusing n and k in complexity
• Thinking sorting is O(n)

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