Loading
Loading
A meetup has a single stage, but the organisers accepted too many talks. Each talk is a row [start, end]; it occupies the stage from start up to, but not including, end. Two talks clash if their times overlap; one talk ending at the minute another starts is fine.
Return the fewest talks that must be dropped so that no two remaining talks clash.
talks = [[1, 2], [2, 3], [3, 4], [1, 3]][1,2] [2,3] [1,3] [3,4]sorted by endkeep [1,2]stage free from 2keep [2,3]starts at 2 — finedrop [1,3]starts before 3keep [3,4]3 kept of 4 → drop 11Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
| 0 | 1 | 2 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 1 | 3 |
Dropping [1,3] leaves three back-to-back talks.
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 | 1 | 2 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 1 | 3 |
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 | 5 |
|---|---|---|
| 1 | 1 | 5 |
| 2 | 1 | 5 |
Three identical talks: only one can stay.