时间戳

首页 > 解决方案 > 事件（开始，完成），1 天的最大事件。c++中的性能问题

c++ - 事件（开始，完成），1 天的最大事件。c++中的性能问题

问题描述

他们给了我 N 组开始/结束时间 EX:(8:45/12:00)。
在返回 MAX 事件后，一个人可以参与而不会重叠。
（一场在 8:00 结束，一场在 8:00 开始，不重叠）。

我已经为每个事件制作了一个带有开始和结束的基础课程。
之后，我做了一个递归函数来制作“事件链”。
我的解决方案在 N < 100 的情况下完成了它的工作，但是因为 O(n!) [我认为] N>100 我的（非常）旧计算机并没有足够快地给我答案。

class Event{
public:
int hh,mm;
int ehh,emm;
};

int chain(Event* array,int nchain,int index,int N){
int max = nchain;
for(int i = 0;i<N;i++){
    if(overlapping(app[index],app[i])){
        int tempmax = chain(array,nchain+1,i,N);
        if(tempmax > max){
            max = tempmax;
        }
    }
}
return max;
}

bool overlapping(Event a,Event b){
    if(a.ehh<b.hh || (a.ehh==b.hh && a.emm<=b.mm) ){
        return true;
    }
    else{
        return false;
    }   
}

标签： c++optimization

解决方案

天真的解决方案可能是 O(2 N ) 但是：

  1. 当子集有内部调度冲突时，您似乎有修剪的逻辑，这已经极大地帮助了复杂性。

  2. 动态编程可以做得更好。这个问题听起来有很好的支配特性——如果一组 N 事件让你在时间 X 空闲，而另一组给你 N+1 事件并且在时间 X 或之前空闲，前者不需要被进一步考虑。

    修剪占主导地位的子集并继续探索最优边界。

另一种观点（导致相同的算法）是考虑到，在包含某个事件 Y 的所有时间表中，在 Y 开始之前做什么的选择和在 Y 结束之后做什么的选择是完全独立的，并且可以分别优化。

我相信，但没有提供证据，您的最终算法将是 O(N 2 )。

推荐阅读