197. Darts for Balloons
Balloons float in a row along a wall. Balloon i covers the horizontal span balloons[i] = [left, right], with both ends included. A dart thrown straight up from position x bursts every balloon whose span contains x, that is, every balloon with left <= x <= right. Darts can be thrown from any integer position and keep flying, so one dart can burst many balloons.
Return the minimum number of darts needed to burst every balloon. The balloons are given in no particular order.
Example 1
- Input:
- balloons = [[1,4],[2,6],[5,9],[10,12]]
- Output:
- 3
- Explanation:
A dart at position 4 bursts the first two balloons, a dart at 9 bursts [5,9], and a dart at 12 bursts [10,12]: 3 darts.
Example 2
- Input:
- balloons = [[3,3],[3,3]]
- Output:
- 1
- Explanation:
Both balloons are the single point 3, so one dart bursts them both.
Example 3
- Input:
- balloons = [[1,2],[3,4],[5,7]]
- Output:
- 3
- Explanation:
No two spans share a position, so each balloon needs its own dart.
Constraints
1 ≤ balloons.length ≤ 105
0 ≤ left ≤ right ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(1)