Book the Most Non-Clashing Workshops in One Hall
Implement maxWorkshops
A 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.
Example 1:
Input: starts = [2,6,1,9,4,8], ends = [5,8,3,12,7,10]
Output: 3
Example 2:
Input: starts = [1,4,7], ends = [4,7,10]
Output: 3
Example 3:
Input: starts = [5,5,5], ends = [6,7,8]
Output: 1
+ 9 hidden test cases run on Submit.
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
starts =
[2, 6, 1, 9, 4, 8]
ends =
[5, 8, 3, 12, 7, 10]