Optimal way to find common negative space in map of student_ids to class_times

Question

I am writing a proof of concept for a scheduling application in PHP. I have a 2D array of the student schedule in the format of (str) class_time => (array) student_ids, printout: http://d.pr/i/UKAy.

At this point in the processing, I need to determine which class_time is the most appropriate to host a new course with say 10 students requesting it. To this end, I would I want to determine how many students have n class_times available, ideally stored as class_time => student_ids => n_available_class_times.

So, what is an ideal way to build/search this data? The end result is a list of all class_times and an idea of what students can utilize a given class as each new course is scheduled. This allows me to sort by available_class_times to find the students who are most constrained in their schedule, and who need priority in being schedule to a given class given how hard it would be to schedule them in the future, given a number of present/potential constraints.

Answer 1

Something as followed would help. Each array student_ids needs to be sorted. You can use quick sort to do that in nlog(n) time. Then you would have to start planning. I think something like AB pruning would work here because you have some optimal states at the end and decisions along the way that affect your optimal state. (the sorting bit at the start is just to make it faster)

Here is some stuff on AB pruning:

To start, there is a decision algorithm called min-max that states that all the decisions in a "game" lead to a final state that is either infinitely good or infinitely bad i.e. winning or losing. So you build this tree each node representing a "game state", in your case a state of students being scheduled. And then you search the tree. Transversing it for best move states. In your case optimal scheduling. At each node, you decide if it is an end state and call it at either infinite or negative infinite or you branch off into other nodes. Note that this is not a binary tree. The decision tree nodes have n branches where n is the number of decisions you can make there. This is not too great for what your doing, but it requires explaining to understand AB pruning.

Now assume that instead of just asking if a node is a win or a lose, you could weight how good of a game state it was. In your case based on the number of students that could be optimally scheduled. The as you tranversed the huge decision tree, you can cut out huge sections because you know they lead to crappy "game states" i.e. states where the students you want easily placed and not easily placed. The way you do this is by considering nodes that lead to game states B that you know to be worst than A (the node you previously evaluated). This is good because searching this tree is a serious computational task. This allows you to evaluate even deeper by ignoring huge sections (something that is really awesome huge computational gain). This gets you your answer of best class schedule states. Good Luck Dude.

// HERE IS SOME CODE FROM THE INTERNET
function alphabeta(node, depth, α, β, Player)         
if  depth = 0 or node is a terminal node
    return the heuristic value of node
if  Player = MaxPlayer
    for each child of node
        α := max(α, alphabeta(child, depth-1, α, β, not(Player) ))     
        if β ≤ α
            break                             (* Beta cut-off *)
    return α
else
    for each child of node
        β := min(β, alphabeta(child, depth-1, α, β, not(Player) ))     
        if β ≤ α
            break                             (* Alpha cut-off *)
    return β
(* Initial call *)
alphabeta(origin, depth, -infinity, +infinity, MaxPlayer)

Here is a link on the subject: http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning