算法，以适应尽可能多的事件成为一个时间表可能 [英] Algorithm to fit as many events into a schedule as possible

问题描述

我试图找到一种算法，可以安排作为许多这些非重叠事件的成日程尽可能（其中根据需要任何这些事件可以被添加或删除从调度）。所有这些事件可以重叠，但我想，以适应尽可能多的人变成了一种日常时间表可能：

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?

推荐答案

我写了一个函数调用generateCombination这需要整型数组范围作为输入，并生成阵列中的事件的所有可能的非重叠的组合。从这个数组，你可以提取范围内的最大的阵列，它们是包含事件的尽可能多的范围。

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;
    }
}

这篇关于算法，以适应尽可能多的事件成为一个时间表可能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！