Loading
Loading
At a fairground stall, paper banners hang across a wall. Banner i stretches horizontally over the closed range [start, end]. A dart thrown at horizontal position x tears through every banner whose range contains x, including banners whose edge is exactly at x.
Return the fewest darts needed to tear every banner.
banners = [[10, 16], [2, 8], [1, 6], [7, 12]][1,6] [2,8] [7,12] [10,16]sorted by enddart at 6tears [1,6] and [2,8][7,12] starts after 6needs a new dart — throw at 12[10,16] contains 12already torn — total 2 darts2Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
| 0 | 10 | 16 |
|---|---|---|
| 1 | 2 | 8 |
| 2 | 1 | 6 |
| 3 | 7 | 12 |
A dart at 6 and a dart at 12 tear all four banners.
Example 2
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(n log n) time · O(n) space
Input. Run your code to watch it work on this input, one line at a time.
| 0 | 10 | 16 |
|---|---|---|
| 1 | 2 | 8 |
| 2 | 1 | 6 |
| 3 | 7 | 12 |
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
| 0 | 1 | 2 |
|---|---|---|
| 1 | 3 | 4 |
| 2 | 5 | 6 |
| 3 | 7 | 8 |
No two banners share a point, so each needs its own dart.