2
$\begingroup$

I would really appreciate any thought on this, or under which category does this problem fall (Interval scheduling, Interval partitioning,...) I am really out of thoughts

I have X number of classes each with starting, and finishing time, and N number of free classrooms. And I want to find the maximum number of non-conflicting classes that can be scheduled in those N classrooms.

What I've tries so far :

- First algorithm:

  • Sort Classes in ascending order according to the finishing time of each class.
  • Starting with the minimal finishing time, pick all the intervals that don't conflict with it and save it in a subset.
  • Repeat the first two steps on the very next interval that conflicts with the one we were working on before.

Why wrong?

Ex: we have 4 classes (1,4) (2,6) (6,7) (4,8) and we want to find the maximum number of non-conflicting ones that can be fit in 2 classes.

  • Starting the algorithm on (1,4) will give me subset {(1,4)(6,7)} that can be fit in the first classroom, and in the second classroom i need to put either (2,6) or (4,8) but not both since they conflict, so in total 3 of those classes can be fit in 2 classrooms using this approach.
  • However in real life you can put {(1,4),(4,8)} in a room and {(2,6),(6,7)} in the other, so all of the classes can be held in the 2 rooms.

- Second algorithm

  • Sort Classes in ascending order according to the starting time of each class.
  • Starting with the minimal starting time, pick all the intervals that don't conflict with it and save it in a subset.
  • Repeat the first two steps on the very next interval that conflicts with the one we were working on before.

Why wrong?

Ex: we have 4 classes (1,2) (2,1000) (6,7) (7,8) and we want to find the maximum number of non-conflicting ones that can be fit in 1 class.

  • Starting the algorithm on (1,2) will give me subset {(1,2)(2,1000)} that can be fit in the first classroom, and that's it, so in total 2 of those classes can be fit in a classroom using this approach.
  • However in real life you can put {(1,2),(6,7),(7,8)} in a room and, so 3 of the classes can be held in a room.
$\endgroup$
  • $\begingroup$ For N=1, this problem is the interval scheduling problem and the two algorithms you described are optimal for it. $\endgroup$ – Daniel Mar 1 at 16:09
0
$\begingroup$

The minimal number of rooms needed can be computed by considering the classes in order of finish times, and if a class can't be fit into any one of the rooms in use, create a new room for it. See e.g. Erickson, "Algorithms", section 4.2.

This is the problem of asking if an interval graph can be colored with $N$ colors (the rooms). Perhaps digging into scheduling nets some algorithm(s). It isn't a problem for which I've seen a simple algorithm. Determining if a general graph is $N$ colorable is NP-complete (i.e., no much better solution expected than just trying all possibilities) if $N \ge 3$, perhaps being an interval graph is enough of a restriction to make it tractable...

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Coloring interval graphs is in P by sorting the intervals by finish time and coloring them greedily. This gives us an optimal N such that ALL classes can be scheduled. However the question is how many vertices one can color with a given number of colors. Maybe the algorithm can be adapted to that. $\endgroup$ – Daniel Mar 1 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.