Algorithm to fit as many events into a schedule as possible

Question

I'm trying to find an algorithm that can arrange as many of these non-overlapping events into a schedule as possible (where any of these events can be added or removed from the schedule as needed). None of these events can overlap, but I want to fit as many of them into a daily schedule as possible:

12:00 PM - 12:45 PM: Lunch

1:00 AM - 3:00 AM: Math class 1

3:30 PM - 5:00 PM: Math class 2

7:00 PM - 10:00 PM: History class 1

9:00 PM - 11:00 PM: History class 2

Any time of day: Grocery shopping, 40 minutes

Any time of day: Study math for 30 minutes

Any time of day between 11:00 AM and 4:00 PM: Basketball practice for 2 hours

I've been thinking about this problem for a while, and I still have no idea about how I should solve it. What type of calendar-scheduling algorithm would be most effective in this case?

Answer 1

You are bin packing periods into a single day length. You want to find the possible solutions for your problem and grade them according to the number of periods you manage to pack into it.

1. Split your day in 15 mins intervals, so that from 1 am to 10 pm you have 21 * 4 frames.
2. Generate every permutation possible with your constraints (no overlap of frames).
3. For each valid permutation, count the number of periods you managed to fit in.
4. Print the [x] permutations that scored the highest

Answer 2

I've written a function called generateCombination that takes an array of integer ranges as input, and generates all possible non-overlapping combinations of the events in the array. From this array, you can extract the largest arrays of ranges, which are the ranges that contain the greatest possible number of events.

http://jsfiddle.net/nvYZ8/1/

var theArray = generateCombination([[0, 2], [2, 3], [4, 5], [0, 9], [2, 50]]);
alert(JSON.stringify(theArray));

function generateCombination(theArray) {
    var theString = "";
    var tempArray = new Array();
    for (var i = 0; i < theArray.length; i++) {
        theString += "1";
    }
    var maximumNumber = convertFromBaseToBase(theString, 2, 10);

    for (var k = 0; k <= maximumNumber; k++) {
        theString = convertFromBaseToBase(k + "", 10, 2);
        while(theString.length != theArray.length){
            theString = "0" + theString;
        }
        var theResult = getArray(theArray, theString);
        if(theResult != false){
            tempArray[tempArray.length] = JSON.stringify(theResult);
        }
    }
    return tempArray;
}

function getArray(theArray, theString){
        var tempArray = new Array();
    for(var i = 0; i < theArray.length; i++){
        if(theString[i] == 1){
            tempArray[tempArray.length] = theArray[i];
        }
    }
        for (var i = 0; i < theArray.length; i++) {
            for (var j = i; j < theArray.length; j++) {
                if ((j != i) && (theString[i] == 1) && (theString[j] == 1)) {
                    //check whether theArray[i] overlaps with theArray[j]
                    var overlaps = rangesOverlap(theArray[i][0], theArray[i][1], theArray[j][0], theArray[j][1]);
                    //if overlaps is true, break out of the current loop
                    //otherwise, add theArray[j] to tempArray
                    if(overlaps == true){
                        return false;
                    }
                }
            }
        }
        return tempArray;
}

function convertFromBaseToBase(str, fromBase, toBase) {
    var num = parseInt(str, fromBase);
    return num.toString(toBase);
}

function rangesOverlap(x1, x2, y1, y2) {
    if (x1 <= y2 && y1 <= x2) {
        return true;
    } else {
        return false;
    }
}

Answer 3

I think Dynamic Programming is the solution ..

For a, b as events: f(a) > f(b) ~ duration(a) < duration(b)

For x, y as schedules: g(x) > g(y) ~ Number-Of-Events(x) > Number-Of-Events(y)

Dynamic Programming with f(event) over g(schedule); to find the optimal schedule

Answer 4

OTOH I can think of two suitable solutions, one with planning algorithms, PopPlan or GraphPlan; the other, you could use simulated annealing.