0
$\begingroup$

I am trying to design an algorithm that would help me distribute in this example case, 'students' to different exam rooms.

All the constraints for this Theoretical problem would be:

[1]"One student can only be at the exam room at a specific time "... meaning that only one student can give an exam in one of the rooms. No two students can share a room even if their exam starting times is exactly same.

[2]The number of rooms used has to remain a minimum.

[3] We could imagine that there are unlimited number of rooms that are available for use.

As inputs I only have the (sorted) exam starting times for students.

Can anyone suggest an algorithm which would always keep the number of "rooms used" to a minimum?

[Note: Multiple students may have the same exact starting times.]

Improve this question
$\endgroup$
3
  • $\begingroup$ Isn't this a duplicate of a recently posted question? $\endgroup$
    – Raphael
    Commented Oct 15, 2017 at 4:31
  • $\begingroup$ distribute […] 'students' to different exam rooms & algorithm [to minimise] the number of "rooms used" Assign all students to room 42 & 51. This question about "distributing" students may be similar. $\endgroup$
    – greybeard
    Commented Oct 15, 2017 at 4:43
  • $\begingroup$ What have you tried? Have you tried proving it NP-complete? Does it remind you of any NP-complete problem you're already familiar with? (Hint: This is a special case of a NP-complete graph problem that you might already be familiar with.) It sounds like this is a theoretical problem, rather than a practical problem. Can you share the source where you encountered the problem? Is it in a course / textbook, and what topic are you studying now? This is a nice exercise, so I will refrain from posting an answer for a little while, to give you a chance to solve it yourself. $\endgroup$
    – D.W. ♦
    Commented Oct 17, 2017 at 5:17

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.