算法将尽可能多的事件放入计划中

Question

我正在尝试找到一种算法,该算法可以将尽可能多的这些非重叠事件安排到一个时间表中(可以根据需要在时间表中添加或删除任何这些事件).这些事件都不会重叠,但我希望尽可能多地将它们纳入每日时间表中:

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

我一直在考虑这个问题,我仍然不知道应该如何解决它.在这种情况下,哪种类型的日历调度算法最有效？

Answer 1

我编写了一个名为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;
    }
}