Minimum Number of Arrows to Burst Balloons

MediumIntervalsgreedy

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Balloons are taped to a wall along the x-axis. Each balloon is given as points[i] = [start, end], meaning it covers every x from start to end inclusive. An arrow shot straight up at position x bursts every balloon with start <= x <= end, and keeps flying. Balloons that only touch at an endpoint can be burst by one arrow at that shared coordinate. Return the minimum number of arrows needed to burst all balloons.

Examples

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
An arrow at x = 6 bursts [2,8] and [1,6]; an arrow at x = 12 bursts [10,16] and [7,12].
Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
No two balloons overlap, so each needs its own arrow.
Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Arrows at x = 2 and x = 4 cover all four balloons.

Constraints

  • 1 <= points.length <= 10^5
  • points[i].length == 2
  • -2^31 <= start <= end <= 2^31 - 1

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More greedy problems