Fewest Talks to Cancel So the Rest Don't Overlap
Implement fewestCancellations
A conference room has been double-booked by several talks, each with a start and an end time. A talk occupies the room from its start up to (not including) its end, so one talk may start at the exact moment another ends. Cancel as few talks as possible so that no two of the remaining talks overlap, and return how many must be cancelled.
Keeping as many talks as possible is the same as cancelling as few as possible. A dynamic-programming table of the longest compatible chain works; a greedy pass that sorts by end time and keeps whatever fits is simpler and faster.
Example 1:
Input: talks = [[1,4],[3,5],[4,8],[6,7],[9,12],[7,10]]
Output: 3
Example 2:
Input: talks = [[3,5],[5,8]]
Output: 0
Example 3:
Input: talks = [[4,6],[4,6],[4,6],[4,6]]
Output: 3
+ 9 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ talks.length ≤ 12; each talk is [start, end] with 0 ≤ start < end ≤ 40 - ●
A talk occupies its room from start up to (not including) end, so a talk may start exactly when another ends; two talks clash only if their time ranges genuinely overlap - ●
You may cancel any talks. Return the fewest cancellations needed so that no two remaining talks clash
talks =