Why it works
- The balloon that ends first must be burst by some arrow at or before its end. Shooting exactly at its end loses nothing: every other balloon such an arrow could burst starts before that end and, ending later, still covers it.
- So each new arrow goes to the end of the first balloon the last arrow missed. A later balloon is missed only if it starts after arrowAt; one that starts at arrowAt is touched and bursts.
- Each new arrow is for a balloon that starts after the previous arrow, so the balloons that got arrows, [2, 4], [7, 9] and [10, 12], share no point. No arrow can burst two of them, so fewer than 3 arrows is impossible.
Complexity
Time O(n log n): the sort; the pass after it is O(n). Memory O(1) besides what the sort needs.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗