| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
How do I solve the interval scheduling problem but instead with k machines, meaning I can put the intervals in K different sets such that in each of the sets none of the intervals overlap and I want the maximum total interval, in O(nlogn) time or less.
Thanks!
I think is the problem you are refferring to ??! CSES Problem
The approach is the same for the question with only one machine the only difference here is as you proceed assigning every interval(sorted as per the ending time) you assign it to the machine which ended it's last job just before the start of this job. This ensures that as soon as a machine gets free it is assigned the next available job. You can see the C++ implementation here.
Why might it not be optimal to pick the first K elements at first and then proceed with the assignment.
whether it will be optimal or not depends on how you proceed and even in the above solution the first k elements are always being picked but not nessesarily by different machines.
Consider the test case
here the optimal solution would be
but if you greedily give the first 2 intervals to different machines the output will be :
This lecture note from the University of Toronto answers your question: http://www.cs.toronto.edu/~milad/csc373/lectures/T1.pdf