java - 平均分配算法

Question

我正在开发事件分发应用程序。我有一长串一个月的 Activity list 。事件对象包含开始时间和结束时间。

public class Event {
    long eventID;

    Calendar startTime;
    Calendar endTime;

    .......
}

我想将上面的列表分成 N 个部分。

Map<Integer, List<Event>> eventLists;

要求是: 每个 block 的大小应该几乎相等，并且每个部分的分布应该在一个月内均匀分布。

是否有适合解决此问题的众所周知的算法。如果有人可以提供准确的解决方案或对任何众所周知的算法的任何引用，我更愿意。

我正在寻找一种具有统计分析的算法。

这是我寻找的一个简单示例。但它应该包含统计分析以平均分配。

Calendar monthStart = EventUtil.getMonthStart();
Calendar monthEnd = EventUtil.getMonthEnd();

Calendar oneDayRange = Calendar.getInstance();
oneDayRange.add(Calendar.DATE, 1);

int index = 0;

while (!monthStart.after(monthEnd)) {

    Iterator<Event> it = events.iterator();

    while (it.hasNext()) {
        Event e = it.next();

        if(!e.getStartTime().before(monthStart) && !e.getStartTime().after(oneDayRange)) {
            eventLists.get(index % N).add(e);
            it.remove();
            index++;
        }

    }

    monthStart.add(Calendar.DATE, 1);
    oneDayRange.add(Calendar.DATE, 1);
}

非常感谢!

Answer 1

如果必须考虑事件持续时间，则所描述的问题是 partition problem 的概括。 ，这是 NP-hard，但承认 polynomial time approximation scheme .如果事件持续时间不重要，并且可以在线性时间内完成对 N 时隙的循环分配。