I am given a problem, that is about scheduling n classes in k rooms at a school, and it is a decision problem, because we want to ask if we can arrange these n classes in those k rooms so that a given timelimit t is not exceeded (the total time of classes in a certain scheduled way should not exceed t).
I am aware about to firstly show that every solution to the problem can be verified in polynomial time, but when it comes to reducing some known NP complete problem to the class-room scheduling problem then I do not know which NP-complete problem I should take.
I was thinking about using Traveling Salesman Problem to reduce, but I am not sure about how to interpret my class-room scheduling problem into a graph considering the symbolics. My first attempt to interpret my problem as a graph is to consider the classes as vertices, rooms as colours and the time for a class denoted by a weighted edge between two classes (the latter two interpretations completely unsure). But I don't know if this follows a standard pattern for some scheduling problem or I don't even know if Traveling Salesman Problem is a good NP-complete problem to reduce to the class-room scheduling problem. In the latter case, then I would like to know examples of more suitable NP-complete problems to reduce in my case.
Thanks in advance!
You can use map-coloring (graph-coloring) for it. You just need to define rules for edges and nodes. Nodes will be classes, rooms will be colors and you connect classes that can't be in same time. This is actually k-coloring problem, where you need to color specific graph with k colors in order to minimize number of classes per color. However in this special case, you just need to have less or equal to t per color. You can achieve this by going by standard rule of coloring, and switch to new color as soon as it has t number of classes.
This is still a NP-complete problem. Only exception is when you have 1 or 2 classes, then its in polynomial time. When you have 1 room, you just need to check if n<=t. When you have 2 rooms, you just need to check if it can be colored by 2 colors. You can achieve this by DFS (but first check if n <= 2t) and color odd steps with first color and even steps with second color. If it is possible to color all nodes with this tactic, you have a positive solution. When k>=3, its NP-complete.