Scheduling Courses
Have you joined Carrots yet?
The Carrot University has already taken in students and have had them sign up for several different courses.
The university is trying to organize the courses into several (non-overlapping) time slots. All courses in the same slot are run concurrently. So that a student may attend all the courses he signed up for, the university requires that different slots are allocated to different courses which have overlapping audiences (i.e, if the same student has signed up for both courses).
To save time, the university wants to organize the courses in as few slots as possible.
Which of the following graph theory problems can this scenario be modeled as?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Construct a graph G ( V , E ) with vertices being the courses. There is an edge between vertices u and v iff there is a student who is taking these two courses simultaneously. Then a minimum coloring of this graph gives the minimum number of required time slots.