Algorithm for the maximum possible number of events in the schedule

Question

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

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 don’t know how I should solve it. What type of scheduling algorithm would be most effective in this case?

Answer 1

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

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 2

You pack in one day. You want to find possible solutions to your problem and evaluate them according to the number of periods in which you can pack.

• Divide your day in 15 minutes so that from 1:00 to 22:00 you have 21 * 4 frames.
• Create every possible permutation with your limitations (without overlapping frames).
• For each permissible permutation, count the number of periods in which you managed to fit.
• Print the largest permutations [x]

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 graphs: g (x)> g (y) ~ Number of events (x)> Number of events (y)

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

Answer 4

OTOH I can present two suitable solutions: one with scheduling algorithms, PopPlan or GraphPlan; another, you can use simulated annealing.