CODEWITHSUNDEEP
combinationsschedule
osolmaz
osolmaz

Reputation: 1923

Algorithm to schedule courses

I currently have a problem that for my senior year, I need to choose 5 elective courses out of 20+ possible courses. All these courses are distributed to weekdays. I need to develop a robust algorithm to show me all possible combinations without overlapping any of the course hours. I am a little bit short of time, so I figured I'd ask here, and it would be of help to other people in the future. My original idea was to try all combinations of 5 out of 20+, and remove the schedules that had overlapping courses. The brute force solution seems easy to implement. Just out of curiosity, would there be another more intelligent solution to this problem? e.g. What if I had 1000+ courses to choose from?

Upvotes: 1

Views: 425

Answers (1)

Origin
Origin

Reputation: 2017

A little bit faster could be to select the first course (out of 1000) and remove all the courses that overlap. Then select the 2nd course out of the remaining courses and remove the overlapping courses again. If you do that 5 times, you will have 5 courses that don't overlap. The last iteration isn't really necessary because once you have 4 courses, then every course that's left will not overlap.

By backtracking you will get all the possible course combinations. An efficient way of backtracking here could be by using dancing links as proposed by Knuth.

Upvotes: 1

Related Questions