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