# Schedule X Classes In N Classrooms

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.
• For N=1, this problem is the interval scheduling problem and the two algorithms you described are optimal for it. – Daniel Mar 1 '20 at 16:09

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...