Start learning free

LESSON 518 OF 635 · INTERVALS

Fewest Arrows to Burst Balloons in JavaScript

Practice O(n log n)

You get an array points. Each pair [start, end] in it is one balloon. The balloon covers every point on a line from its start to its end.

An arrow shot at point x bursts every balloon with start <= x <= end. Return the fewest arrows that burst all the balloons.

Balloons can overlap. One arrow can burst several of them.

 

Example 1:

Input: points = [[-4,2],[0,6],[5,9],[1,3],[8,8]]
Output: 2
Explanation: An arrow at x = 2 bursts [-4,2], [0,6] and [1,3].
An arrow at x = 8 bursts [5,9] and [8,8].
[-4,2] and [8,8] share no point.
So one arrow is not enough.

Example 2:

Input: points = [[0,20],[3,4],[6,8],[15,30]]
Output: 3
Explanation: [3,4], [6,8] and [15,30] share no point.
So each one needs its own arrow.
[0,20] contains [3,4], so the same arrow bursts it.

Example 3:

Input: points = [[1,3],[3,6]]
Output: 1
Explanation: Both balloons cover the point 3.
One arrow at x = 3 bursts both.

 

Constraints:

  • 1 to 100,000 balloons.
  • Each start and end is a whole number from -231 to 231 - 1.
  • No start is greater than its end.
  • The balloons come in any order.

Note:

Your solution should run in O(n log n) time.

STEP 1 OF 8
    Ctrl + Enter to check

    Minimum Number Of Arrows To Burst Balloons in JavaScript

    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free