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.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
