Minimum Number of Arrows to Burst Balloons

🎯

Minimum Number of Arrows to Burst Balloons

mediumINTERVALSAmazonGoogleFacebook

Imagine you have a set of balloons floating along a horizontal line, each balloon occupying a segment. You want to shoot arrows vertically to burst all balloons using as few arrows as possible.

💡 This problem is about intervals and grouping overlapping intervals efficiently. Beginners often struggle because they try to consider every balloon individually rather than leveraging interval sorting and greedy strategies to minimize the number of arrows.

📋

Problem Statement

You are given an array points where points[i] = [start_i, end_i] represents the horizontal diameter of a balloon. An arrow can be shot vertically along the x-axis at any point x, bursting all balloons whose diameters intersect x. Return the minimum number of arrows that must be shot to burst all balloons.

1 ≤ points.length ≤ 10^5-2^31 ≤ start_i < end_i ≤ 2^31 - 1

💡

Example

Input"[[10,16],[2,8],[1,6],[7,12]]"

Output2

Shoot one arrow at x = 6 to burst balloons [2,8] and [1,6], and another arrow at x = 11 to burst balloons [10,16] and [7,12].

• Only one balloon → 1 arrow
• All balloons non-overlapping → number of balloons arrows
• All balloons fully overlapping → 1 arrow
• Balloons with negative coordinates → handled correctly

⚠️

Common Mistakes

Sorting by start coordinate but not updating the current group's end correctly

Incorrect arrow count due to missing overlaps

✅ Always update the group's end to the minimum end of overlapping balloons

Sorting by end coordinate but shooting arrow at start instead of end

Misses bursting some balloons, leading to wrong answer

✅ Always shoot arrow at the end coordinate of the earliest finishing balloon

Not handling empty input array

Runtime error or wrong output

✅ Check if input is empty and return 0 immediately

Using 'start >= current_end' instead of 'start > current_end' when deciding new arrow

Overcounts arrows because touching intervals are considered non-overlapping

✅ Use strict greater than '>' to allow bursting balloons that touch at endpoints

🧠

Brute Force (Check All Overlaps with Nested Loops)

💡 This approach exists to build intuition by directly checking overlaps between every pair of balloons. It is simple but inefficient, illustrating why optimization is needed.

Intuition

Try shooting an arrow for each balloon and check which other balloons it can burst by overlapping intervals. Count how many arrows are needed by grouping overlapping balloons.

Algorithm

1. Sort balloons by their start coordinate to ensure consistent grouping.
2. Initialize a count of arrows to 0 and a visited set to track burst balloons.
3. For each balloon not yet burst, shoot an arrow at its start point.
4. Mark all balloons overlapping with this arrow as burst.
5. Repeat until all balloons are burst.

💡 The nested loops make it hard to see efficiency, but this method guarantees correctness by explicitly grouping overlapping balloons.

</>

Code

def findMinArrowShots(points):
    n = len(points)
    if n == 0:
        return 0
    points.sort(key=lambda x: x[0])  # Sort to group overlaps correctly
    visited = [False] * n
    arrows = 0
    for i in range(n):
        if not visited[i]:
            arrows += 1
            x_start, x_end = points[i]
            for j in range(i + 1, n):
                if not visited[j]:
                    # Check if balloons overlap
                    if points[j][0] <= x_end and points[j][1] >= x_start:
                        visited[j] = True
            visited[i] = True
    return arrows

# Driver code
points = [[10,16],[2,8],[1,6],[7,12]]
print(findMinArrowShots(points))  # Output: 2

Line Notes

points.sort(key=lambda x: x[0])Sort balloons by start to ensure consistent grouping of overlaps

visited = [False] * nTrack which balloons have been burst to avoid double counting

for i in range(n):Iterate over each balloon to decide if we need a new arrow

if not visited[i]:Only consider balloons not yet burst

for j in range(i + 1, n):Check all subsequent balloons for overlap with current balloon

import java.util.*;
public class Solution {
    public int findMinArrowShots(int[][] points) {
        int n = points.length;
        if (n == 0) return 0;
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0])); // Sort by start
        boolean[] visited = new boolean[n];
        int arrows = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                arrows++;
                int start = points[i][0], end = points[i][1];
                for (int j = i + 1; j < n; j++) {
                    if (!visited[j]) {
                        if (points[j][0] <= end && points[j][1] >= start) {
                            visited[j] = true;
                        }
                    }
                }
                visited[i] = true;
            }
        }
        return arrows;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] points = {{10,16},{2,8},{1,6},{7,12}};
        System.out.println(sol.findMinArrowShots(points)); // Output: 2
    }
}

Line Notes

Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));Sort balloons by start coordinate for consistent grouping

boolean[] visited = new boolean[n];Keep track of burst balloons to avoid recounting

for (int i = 0; i < n; i++) {Iterate over all balloons to find groups

if (!visited[i]) {Process only unburst balloons

for (int j = i + 1; j < n; j++) {Check all subsequent balloons for overlap

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

int findMinArrowShots(vector<vector<int>>& points) {
    int n = points.size();
    if (n == 0) return 0;
    sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    vector<bool> visited(n, false);
    int arrows = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            arrows++;
            int start = points[i][0], end = points[i][1];
            for (int j = i + 1; j < n; j++) {
                if (!visited[j]) {
                    if (points[j][0] <= end && points[j][1] >= start) {
                        visited[j] = true;
                    }
                }
            }
            visited[i] = true;
        }
    }
    return arrows;
}

int main() {
    vector<vector<int>> points = {{10,16},{2,8},{1,6},{7,12}};
    cout << findMinArrowShots(points) << endl; // Output: 2
    return 0;
}

Line Notes

sort(points.begin(), points.end(), ...Sort balloons by start coordinate to process sequentially

vector<bool> visited(n, false);Track which balloons are burst to prevent double counting

for (int i = 0; i < n; i++) {Outer loop to pick each balloon

if (!visited[i]) {Process only balloons not yet burst

for (int j = i + 1; j < n; j++) {Check all other balloons for overlap

function findMinArrowShots(points) {
    const n = points.length;
    if (n === 0) return 0;
    points.sort((a, b) => a[0] - b[0]); // Sort by start
    const visited = new Array(n).fill(false);
    let arrows = 0;
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            arrows++;
            const [start, end] = points[i];
            for (let j = i + 1; j < n; j++) {
                if (!visited[j]) {
                    if (points[j][0] <= end && points[j][1] >= start) {
                        visited[j] = true;
                    }
                }
            }
            visited[i] = true;
        }
    }
    return arrows;
}

// Driver code
const points = [[10,16],[2,8],[1,6],[7,12]];
console.log(findMinArrowShots(points)); // Output: 2

Line Notes

points.sort((a, b) => a[0] - b[0]);Sort balloons by start coordinate for ordered processing

const visited = new Array(n).fill(false);Keep track of balloons already burst

for (let i = 0; i < n; i++) {Iterate over each balloon to decide if arrow needed

if (!visited[i]) {Only consider balloons not yet burst

for (let j = i + 1; j < n; j++) {Check all other balloons for overlap

⏱

Complexity

TimeO(n^2)

SpaceO(n)

We check each balloon against every other balloon, resulting in a nested loop of n*n. The visited array uses O(n) space.

💡 For n=20, this means about 400 comparisons, which is manageable, but for n=100000 it becomes 10 billion operations, which is too slow.

Interview Verdict: TLE / Use only to introduce problem

This approach is too slow for large inputs but helps understand the problem and why optimization is needed.

🧠

Sorting + Greedy by Start (Improved Overlap Grouping)

💡 Sorting balloons by their start coordinate helps group overlapping balloons more efficiently than brute force, but this approach still has inefficiencies.

Intuition

Sort balloons by start coordinate and iterate through them, merging overlapping balloons into groups that can be burst by one arrow.

Algorithm

1. Sort balloons by their start coordinate.
2. Initialize arrow count to 1 and track the end of the current overlapping group.
3. Iterate through balloons; if a balloon starts after the current group's end, increment arrow count and update group end.
4. Otherwise, update the group's end to the minimum end of overlapping balloons.

💡 This approach reduces unnecessary comparisons by leveraging sorted order and tracking overlap boundaries.

</>

Code

def findMinArrowShots(points):
    if not points:
        return 0
    points.sort(key=lambda x: x[0])
    arrows = 1
    current_end = points[0][1]
    for start, end in points[1:]:
        if start > current_end:
            arrows += 1
            current_end = end
        else:
            current_end = min(current_end, end)
    return arrows

# Driver code
points = [[10,16],[2,8],[1,6],[7,12]]
print(findMinArrowShots(points))  # Output: 2

Line Notes

if not points:Handle empty input to avoid errors

points.sort(key=lambda x: x[0])Sort balloons by their start coordinate to process in order

arrows = 1At least one arrow is needed initially

if start > current_end:If current balloon starts after previous group's end, need new arrow

current_end = min(current_end, end)Update group end to the smallest end to maximize overlap

import java.util.*;
public class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        int arrows = 1;
        int currentEnd = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > currentEnd) {
                arrows++;
                currentEnd = points[i][1];
            } else {
                currentEnd = Math.min(currentEnd, points[i][1]);
            }
        }
        return arrows;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] points = {{10,16},{2,8},{1,6},{7,12}};
        System.out.println(sol.findMinArrowShots(points)); // Output: 2
    }
}

Line Notes

if (points.length == 0) return 0;Handle empty input to avoid runtime errors

Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));Sort balloons by start coordinate for ordered processing

int arrows = 1;Start with one arrow for the first balloon group

if (points[i][0] > currentEnd) {New arrow needed if balloon starts after current group's end

currentEnd = Math.min(currentEnd, points[i][1]);Update group end to smallest end to maximize overlap

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

int findMinArrowShots(vector<vector<int>>& points) {
    if (points.empty()) return 0;
    sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    int arrows = 1;
    int currentEnd = points[0][1];
    for (int i = 1; i < points.size(); i++) {
        if (points[i][0] > currentEnd) {
            arrows++;
            currentEnd = points[i][1];
        } else {
            currentEnd = min(currentEnd, points[i][1]);
        }
    }
    return arrows;
}

int main() {
    vector<vector<int>> points = {{10,16},{2,8},{1,6},{7,12}};
    cout << findMinArrowShots(points) << endl; // Output: 2
    return 0;
}

Line Notes

if (points.empty()) return 0;Handle empty input to avoid errors

sort(points.begin(), points.end(), ...Sort balloons by start coordinate to process sequentially

int arrows = 1;Initialize arrow count to one for first group

if (points[i][0] > currentEnd) {Need new arrow if balloon starts after current group's end

currentEnd = min(currentEnd, points[i][1]);Update group's end to smallest end to keep overlap tight

function findMinArrowShots(points) {
    if (points.length === 0) return 0;
    points.sort((a, b) => a[0] - b[0]);
    let arrows = 1;
    let currentEnd = points[0][1];
    for (let i = 1; i < points.length; i++) {
        if (points[i][0] > currentEnd) {
            arrows++;
            currentEnd = points[i][1];
        } else {
            currentEnd = Math.min(currentEnd, points[i][1]);
        }
    }
    return arrows;
}

// Driver code
const points = [[10,16],[2,8],[1,6],[7,12]];
console.log(findMinArrowShots(points)); // Output: 2

Line Notes

if (points.length === 0) return 0;Handle empty input to avoid runtime errors

points.sort((a, b) => a[0] - b[0]);Sort balloons by start coordinate for ordered traversal

let arrows = 1;Start with one arrow for the first overlapping group

if (points[i][0] > currentEnd) {If balloon starts after current group's end, need new arrow

currentEnd = Math.min(currentEnd, points[i][1]);Update group's end to smallest end to maximize overlap

⏱

Complexity

TimeO(n log n)

SpaceO(1)

Sorting takes O(n log n), and a single pass through the sorted array is O(n). No extra space besides variables.

💡 For n=100000, sorting is feasible and the linear scan is efficient, making this approach practical.

Interview Verdict: Accepted but can be improved

This approach is correct and efficient enough for many cases but can be optimized further by sorting by end coordinate.

🧠

Optimal Greedy by Sorting on End Coordinate

💡 Sorting balloons by their end coordinate and greedily shooting arrows at the earliest possible end point minimizes the number of arrows needed.

Intuition

By always shooting an arrow at the end of the earliest finishing balloon, we maximize the number of balloons burst with one arrow.

Algorithm

1. Sort balloons by their end coordinate in ascending order.
2. Initialize arrow count to 1 and set arrow position to the end of the first balloon.
3. Iterate through the balloons; if a balloon starts after the arrow position, shoot a new arrow at its end and increment arrow count.
4. Return the total arrow count.

💡 This greedy strategy ensures each arrow bursts the maximum possible balloons by shooting at the earliest finishing balloon's end.

</>

Code

def findMinArrowShots(points):
    if not points:
        return 0
    points.sort(key=lambda x: x[1])
    arrows = 1
    arrow_pos = points[0][1]
    for start, end in points[1:]:
        if start > arrow_pos:
            arrows += 1
            arrow_pos = end
    return arrows

# Driver code
points = [[10,16],[2,8],[1,6],[7,12]]
print(findMinArrowShots(points))  # Output: 2

Line Notes

if not points:Handle empty input to avoid errors

points.sort(key=lambda x: x[1])Sort balloons by their end coordinate to prioritize earliest finishing

arrows = 1Start with one arrow for the first balloon

arrow_pos = points[0][1]Place arrow at end of first balloon to burst it and overlapping balloons

if start > arrow_pos:If balloon starts after arrow position, need a new arrow

import java.util.*;
public class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        int arrows = 1;
        int arrowPos = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > arrowPos) {
                arrows++;
                arrowPos = points[i][1];
            }
        }
        return arrows;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] points = {{10,16},{2,8},{1,6},{7,12}};
        System.out.println(sol.findMinArrowShots(points)); // Output: 2
    }
}

Line Notes

if (points.length == 0) return 0;Handle empty input to avoid runtime errors

Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));Sort balloons by end coordinate to shoot arrows optimally

int arrows = 1;Initialize arrow count to one for first balloon

int arrowPos = points[0][1];Place arrow at end of first balloon

if (points[i][0] > arrowPos) {Shoot new arrow if balloon starts after last arrow position

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

int findMinArrowShots(vector<vector<int>>& points) {
    if (points.empty()) return 0;
    sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });
    int arrows = 1;
    int arrowPos = points[0][1];
    for (int i = 1; i < points.size(); i++) {
        if (points[i][0] > arrowPos) {
            arrows++;
            arrowPos = points[i][1];
        }
    }
    return arrows;
}

int main() {
    vector<vector<int>> points = {{10,16},{2,8},{1,6},{7,12}};
    cout << findMinArrowShots(points) << endl; // Output: 2
    return 0;
}

Line Notes

if (points.empty()) return 0;Handle empty input to avoid errors

sort(points.begin(), points.end(), ...Sort balloons by their end coordinate to prioritize earliest finishing

int arrows = 1;Start with one arrow for the first balloon

int arrowPos = points[0][1];Place arrow at end of first balloon

if (points[i][0] > arrowPos) {If balloon starts after arrow position, shoot new arrow

function findMinArrowShots(points) {
    if (points.length === 0) return 0;
    points.sort((a, b) => a[1] - b[1]);
    let arrows = 1;
    let arrowPos = points[0][1];
    for (let i = 1; i < points.length; i++) {
        if (points[i][0] > arrowPos) {
            arrows++;
            arrowPos = points[i][1];
        }
    }
    return arrows;
}

// Driver code
const points = [[10,16],[2,8],[1,6],[7,12]];
console.log(findMinArrowShots(points)); // Output: 2

Line Notes

if (points.length === 0) return 0;Handle empty input to avoid runtime errors

points.sort((a, b) => a[1] - b[1]);Sort balloons by end coordinate to shoot arrows optimally

let arrows = 1;Initialize arrow count to one for first balloon

let arrowPos = points[0][1];Place arrow at end of first balloon

if (points[i][0] > arrowPos) {Shoot new arrow if balloon starts after last arrow position

⏱

Complexity

TimeO(n log n)

SpaceO(1)

Sorting takes O(n log n), and a single pass through the sorted array is O(n). No extra space besides variables.

💡 This approach is efficient and scalable for large inputs, making it ideal for interviews.

Interview Verdict: Accepted / Optimal

This is the best known approach for this problem and should be implemented in interviews after explaining simpler methods.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the optimal greedy approach (Approach 3). Brute force is useful to explain but not to implement fully.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code
2. Sorting + Greedy by Start	O(n log n)	O(1)	No	N/A	Explain as intermediate step
3. Optimal Greedy by Sorting on End	O(n log n)	O(1)	No	Yes (arrow positions)	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force to show understanding, and finally present the optimal greedy solution.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding of the problem.Step 3: Improve to sorting by start coordinate and greedy grouping.Step 4: Present the optimal greedy approach by sorting on end coordinate.Step 5: Code the optimal solution and test with examples.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your ability to recognize interval scheduling patterns, optimize from brute force to greedy, and write clean, correct code.

Common Follow-ups

• What if balloons are given in a stream? → Use a data structure to maintain intervals dynamically.
• Can you return the actual arrow positions? → Track arrow positions when shooting.

💡 Follow-ups test your ability to adapt the solution to dynamic inputs and extend it to return more information.

🔍

Pattern Recognition

When to Use

Use this pattern when you have intervals and need to minimize the number of points (arrows) to cover all intervals, especially when intervals can overlap.

Signature Phrases

'minimum number of arrows to burst all balloons''intervals overlapping on a line'

NOT This Pattern When

Problems that require maximum number of non-overlapping intervals or interval partitioning with resource allocation are different patterns.

Similar Problems

Non-overlapping Intervals - minimize removals to avoid overlapsMeeting Rooms II - find minimum rooms to hold all meetingsInterval List Intersections - find intersections between interval lists

Practice

1. You are given a stream of integers arriving one by one. After each insertion, you need to maintain a list of disjoint intervals that cover all the numbers seen so far, merging intervals if necessary. Which algorithmic approach best guarantees efficient insertion and interval merging in this scenario?

easy

A. Use a brute force approach by storing all numbers and sorting them each time intervals are requested.

B. Use dynamic programming to precompute all possible intervals and update them incrementally.

C. Use a balanced tree or sorted container to insert intervals and merge them on each insertion efficiently.

D. Use a greedy algorithm that merges intervals only when requested, without maintaining sorted order.

Solution

1. Step 1: Understand the problem constraints

   The problem requires maintaining disjoint intervals dynamically as numbers arrive, with efficient insertion and merging.

2. Step 2: Evaluate approaches

   Brute force sorting each time (A) is inefficient. Dynamic programming (B) is not suitable for dynamic interval merging. Greedy merging only on request (D) leads to inefficient queries. Balanced tree or sorted container (C) supports O(log n) insertion and merging, making it optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Balanced tree supports efficient insertion and merging [OK]

Hint: Balanced tree supports efficient dynamic interval merging [OK]

Common Mistakes:

• Thinking brute force sorting is efficient enough
• Confusing DP with interval merging
• Assuming greedy merging on request is optimal

2. The following code attempts to count intervals containing each point using a line sweep. Identify the bug that causes incorrect counts for points exactly at interval ends.

medium

A. Line adding interval end event should use end + 1 instead of end.

B. Sorting key should sort points before interval starts.

C. Active count should be incremented after processing points, not before.

D. Result array initialization size is incorrect.

Solution

1. Step 1: Identify event creation for interval ends

   Interval end events use 'end' instead of 'end + 1', so points exactly at interval end are processed after the interval ends.

2. Step 2: Understand effect on counting

   Because end events are processed at 'end', points at 'end' see active count after decrement, missing that interval.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to end + 1 fixes counting for points at interval ends [OK]

Hint: Interval end event must be at end+1 to include points at end [OK]

Common Mistakes:

• Using end instead of end+1
• Misordering events
• Incorrect active count update

3. What is the time complexity of the addNum operation in the optimal balanced tree approach for maintaining disjoint intervals, assuming there are n intervals stored?

medium

A. O(n) because intervals need to be scanned linearly for merging

B. O(log n) due to binary search and limited merging operations

C. O(n log n) because each insertion requires sorting intervals

D. O(1) since insertion is always at the end or start

Solution

1. Step 1: Identify main operations in addNum

   addNum uses binary search (bisect_left) to find insertion index in O(log n).

2. Step 2: Analyze merging cost

   Merging involves at most constant number of interval merges (left, right, or both), so O(1) extra work.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search dominates, merges are constant time [OK]

Hint: Binary search + constant merges -> O(log n) [OK]

Common Mistakes:

• Assuming linear scan for merging
• Confusing sorting cost per insertion
• Ignoring constant merge steps

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. What is the time complexity of the binary search + preprocessing approach for the Minimum Interval to Include Each Query problem, given n intervals and m queries?

medium

A. O(n log n + m n log n)

B. O(n log n + m log n * n)

C. O((n + m) log n)

D. O(n * m)

Solution

1. Step 1: Analyze preprocessing

   Sorting intervals by length takes O(n log n).

2. Step 2: Analyze per query cost

   For each query, binary search over lengths is O(log n), but coverage check scans up to O(n) intervals, so O(n log n) per query.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(n log n + m n log n) due to coverage scanning [OK]

Hint: Coverage check inside binary search causes O(n) scan per query [OK]

Common Mistakes:

• Assuming coverage check is O(log n) ignoring linear scan
• Confusing n and m in complexity
• Forgetting sorting cost