尽可能安排更多事件的算法

Question

尽可能安排更多事件的算法

7

我正在尝试寻找一种算法，能够将尽可能多的这些不重叠事件安排到日程中（其中任何一个事件都可以根据需要添加或删除）。这些事件中没有一个可以重叠，但我想尽可能地安排更多的事件在每日日程中：

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

我已经思考这个问题有一段时间了，但仍然不知道该如何解决。在这种情况下，哪种类型的日历调度算法最有效？

- Anderson Green

我仍然不知道这个问题更适合发布在 http://stackoverflow.com/ 还是 http://math.stackexchange.com/ 上。 - Anderson Green

https://dev59.com/xXE85IYBdhLWcg3wgDpI?rq=1 - user177800

@JarrodRoberson 那个问题的描述不够清晰，也不清楚 OP 是否真的想尽可能多地安排日程。我不确定它是否真的是一个重复的问题。 - Anderson Green

@AlbusShin 可能无法将所有事件都安排在日历中。我想尽可能地安排尽可能多的事件进入日历。 - Anderson Green

相关：在Python中实现O(n log n)算法的最大非重叠计数 - jfs

显示剩余7条评论

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

- Anderson Green

我在了解约束编程语言之前就写下了这个答案。有一种名为MiniZinc的编程语言可以更轻松地解决像这样的问题。 - Anderson Green

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)在g(schedule)上的动态规划；以找到最佳日程安排

- Khaled.K

~符号代表什么？ - Anderson Green

f(event) = duration(event)，意为“对于一个事件，其持续时间为f(event)”。g(schedule) = Number-Of-Events(schedule)，意为“对于一个日程安排，其中的事件数量为g(schedule)”。 - Khaled.K

0

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

- Adrian Panasiuk

根据这个谷歌搜索，"PopPlan"通常指的是“仅限高级计划”。你是在指其他的东西吗？ - Anderson Green

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric · Accepted Answer

你正在将时间段压缩到一天中，想要找出可能的解决方案并根据你成功压缩的时间段数量进行评分。

将一天分成15分钟的间隔，从凌晨1点到晚上10点，你会有21 * 4个时间段。
在不重叠的情况下，生成所有可能的排列组合。
对于每个有效的排列组合，计算你成功压缩的时间段数量。
打印得分最高的[x]个排列组合。