Timeline for Job scheduling: algorithm to find the maximum number of overlapping jobs?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 8, 2019 at 8:20 | history | edited | Doc Brown | CC BY-SA 4.0 | Some typos fixed |
| Sep 13, 2016 at 17:17 | history | edited | Doc Brown | CC BY-SA 3.0 | added 172 characters in body |
| Sep 13, 2016 at 17:13 | comment | added | Doc Brown | @Liz: of course, you need to put triplets (time, isStartOrEndpoint, jobnumber) into the array, where isStartOrEndpoint is a boolean flag indicating the type. | |
| Sep 13, 2016 at 15:21 | comment | added | Liz | @DocBrown This is a very efficient method... Basically push active jobs to a data structure, and then remove the job associated with an endpoint from the active jobs when an endpoint is reached when iterating over all the intervals. Although I am wondering with this method, how would one distinguish between a start or end point? Because previously I had two arrays to distinguish between the two... Anyway, I'm sure I'll figure it out, thanks a lot! | |
| Sep 13, 2016 at 14:53 | vote | accept | Liz | ||
| Sep 13, 2016 at 9:36 | history | edited | Doc Brown | CC BY-SA 3.0 | deleted 347 characters in body |
| Sep 13, 2016 at 9:24 | comment | added | Doc Brown | @kevincline: the OPs example showed clearly his intention was to combine A, B, and C in one group for this case (note J2 and J4 do not overlap). In graph terms, the task is to find a connected subgraph, not a fully connected subgraph. And that is what the algorithm described in my answer does. | |
| Sep 12, 2016 at 21:15 | comment | added | kevin cline | What if A overlaps B and B overlaps C but A does not overlap C ? | |
| Sep 12, 2016 at 20:29 | history | edited | Doc Brown | CC BY-SA 3.0 | added 615 characters in body |
| Sep 12, 2016 at 20:20 | history | answered | Doc Brown | CC BY-SA 3.0 |