6

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?

4

4 回答 4

2

我编写了一个名为 generateCombination 的函数，该函数将整数范围数组作为输入，并生成数组中所有可能的非重叠事件组合。从这个数组中，您可以提取最大的范围数组，即包含尽可能多的事件的范围。

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;
    }
}
于 2013-05-20T05:18:54.113 回答
2

您正在将时间段打包成一天的长度。您想为您的问题找到可能的解决方案，并根据您设法打包的时间段数对它们进行评分。

  1. 以 15 分钟为间隔划分一天，这样从上午 1 点到晚上 10 点，您有 21 * 4 帧。
  2. 使用您的约束生成所有可能的排列（帧没有重叠）。
  3. 对于每个有效的排列，计算你设法适应的周期数。
  4. 打印得分最高的 [x] 排列
于 2013-05-20T03:52:41.680 回答
0

OTOH 我能想到两种合适的解决方案，一种是规划算法，PopPlan 或 GraphPlan；另一个，你可以使用模拟退火。

于 2013-06-13T00:58:07.300 回答
0

我认为动态编程是解决方案..

对于 a, b 作为事件：f(a) > f(b) ~ duration(a) < duration(b)

对于 x, y 作为时间表：g(x) > g(y) ~ Number-Of-Events(x) > Number-Of-Events(y)

f(event) over g(schedule) 的动态规划；找到最佳时间表

于 2013-05-20T08:52:55.047 回答