Fewest Talks to Cancel So the Rest Don't Overlap
Solve this ProblemA 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.
Test Case 1:
Test Case 2:
Test Case 3:
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
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Longest Chain of Compatible Talks by Dynamic Programming
BruteKeeping the most talks is the same as finding the longest chain of talks where each one starts at or after the previous one ends; the answer is then n minus that length. Sort the talks by start time and let chain[i] be the longest chain that ends with talk i: it is 1 plus the best chain[j] over every earlier talk j that ends at or before talk i starts. Checking every earlier talk for every talk makes this O(n²), and it makes no assumption about which talks to prefer — it simply tries every predecessor.
O(n²)O(n)1class Solution {
2 public int fewestCancellations(int[][] talks) {
3 int n = talks.length;
4 int[][] byStart = talks.clone();
5 Arrays.sort(byStart, (a, b) -> a[0] - b[0]);
6 int[] chain = new int[n];
7 int longest = 0;
8 for (int i = 0; i < n; i++) {
9 chain[i] = 1;
10 for (int j = 0; j < i; j++) {
11 if (byStart[j][1] <= byStart[i][0]) chain[i] = Math.max(chain[i], chain[j] + 1);
12 }
13 longest = Math.max(longest, chain[i]);
14 }
15 return n - longest;
16 }
17}Optimal — Sort by End Time and Keep Whatever Fits
OptimalThe same "keep as many as possible" goal has a greedy solution: sort by end time and always keep the talk that ends soonest, then skip anything that starts before the last kept talk ends. The earliest-ending talk blocks the room for the shortest time, so keeping it never reduces what can follow. The talks that get skipped are exactly the cancellations, so the answer is n minus the number kept.
O(n log n)O(n)1class Solution {
2 public int fewestCancellations(int[][] talks) {
3 int[][] byEnd = talks.clone();
4 Arrays.sort(byEnd, (a, b) -> a[1] - b[1]);
5 int kept = 0, lastEnd = Integer.MIN_VALUE;
6 for (int[] talk : byEnd) {
7 if (talk[0] >= lastEnd) {
8 kept++;
9 lastEnd = talk[1];
10 }
11 }
12 return talks.length - kept;
13 }
14}