Book the Most Non-Clashing Workshops in One Hall
Solve this ProblemA hall hosts workshops. Each workshop has a start and an end time and occupies the hall from its start up to (but not including) its end, so a workshop may begin at the very moment another one ends. Choose as many workshops as possible so that no two of them overlap, and return how many that is.
Testing every combination works but explodes as workshops are added. The greedy insight: always hold the workshop that finishes soonest, then repeat with what still fits.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ starts.length ≤ 12, and ends.length equals starts.length - ◆
0 ≤ starts[i] < ends[i] ≤ 40; workshop i occupies the hall from starts[i] up to (but not including) ends[i] - ◆
Two workshops clash only if their time ranges overlap: a workshop may start exactly when another ends - ◆
Return the largest number of workshops that can be held with no clashes
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Test Every Subset of Workshops for Clashes
BruteTry every subset of workshops (a bitmask). For each subset, compare every pair of chosen workshops: two workshops [s₁, e₁) and [s₂, e₂) clash exactly when s₁ < e₂ and s₂ < e₁. If no pair clashes, the subset is valid and its size is a candidate answer. The largest valid size wins. It is guaranteed correct because it checks every possibility, but there are 2ⁿ subsets and each takes up to n² pair checks.
O(2ⁿ · n²)O(1)1class Solution {
2 public int maxWorkshops(int[] starts, int[] ends) {
3 int n = starts.length;
4 int best = 0;
5 for (int mask = 1; mask < (1 << n); mask++) {
6 boolean clash = false;
7 int count = 0;
8 for (int i = 0; i < n && !clash; i++) {
9 if ((mask & (1 << i)) == 0) continue;
10 count++;
11 for (int j = i + 1; j < n; j++) {
12 if ((mask & (1 << j)) != 0 && starts[i] < ends[j] && starts[j] < ends[i]) {
13 clash = true;
14 break;
15 }
16 }
17 }
18 if (!clash) best = Math.max(best, count);
19 }
20 return best;
21 }
22}Optimal — Sort by Finish Time and Take What Fits
OptimalThe workshop that finishes earliest leaves the most room for everything else, so it is always safe to hold it. Sort the workshops by end time; walk through them in that order, remembering when the last chosen workshop ended. If the next workshop starts at or after that time it fits — hold it and update the end time; otherwise skip it. A workshop that is skipped clashes with the one that was already chosen, and the chosen one finishes no later, so nothing is lost by skipping.
O(n log n)O(n)1class Solution {
2 public int maxWorkshops(int[] starts, int[] ends) {
3 int n = starts.length;
4 Integer[] order = new Integer[n];
5 for (int i = 0; i < n; i++) order[i] = i;
6 Arrays.sort(order, (a, b) -> ends[a] != ends[b] ? ends[a] - ends[b] : starts[a] - starts[b]);
7 int count = 0, lastEnd = Integer.MIN_VALUE;
8 for (int idx : order) {
9 if (starts[idx] >= lastEnd) {
10 count++;
11 lastEnd = ends[idx];
12 }
13 }
14 return count;
15 }
16}