Блог

Они дают мне N наборов времени начала / окончания, НАПРИМЕР: (8: 45/12:00).
После возврата МАКСИМАЛЬНОГО количества событий, в которых один человек может участвовать без дублирования.
(одно событие заканчивается в 8:00 и одно начинается в 8: 00, не перекрываются).

Я создал базовый класс с start amp; finish для каждого события.
После этого я создал рекурсивную функцию для создания «цепочки событий».
Мое решение выполняет свою работу при 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 amp;amp; a.emm<=b.mm) ){
        return true;
    }
    else{
        return false;
    }   
}
  

Наивным решением может быть O (2 ^N), но:

1. Похоже, у вас есть логика для сокращения, когда подмножество имеет внутренний конфликт планирования, что уже значительно усложнило задачу.

2. Вы можете добиться гораздо большего с помощью динамического программирования. Похоже, что у этой проблемы очень хорошие характеристики доминирования — если один набор из N событий оставляет вас свободными в момент времени X, а другой набор дает вам N 1 событий и освобождает в момент времени X или раньше, то первое не нужно рассматривать дальше.

   Сократите доминирующие подмножества и продолжайте исследовать оптимальные границы.

Другая перспектива (которая приводит к тому же алгоритму) заключается в том, чтобы учитывать, что из всех расписаний, которые включают определенное событие Y, выбор того, что делать до начала Y, и выбор того, что делать после окончания Y, полностью независимы и могут быть оптимизированы отдельно.

Я верю, но не предлагаю доказательств, что ваш окончательный алгоритм будет O (N²).

Есть лучший подход к этой проблеме с использованием жадного решения. Сначала нам нужно отсортировать события по времени завершения в порядке возрастания. Таким образом, всегда оптимально выбирать следующее событие в массиве, которое не перекрывается с набором выбранных событий. Временная сложность будет равна O (nlogn).

 #include<algorithm>
class Event{
    public:
    int hh,mm;
    int ehh,emm;
};

bool overlapping(Event a, Event b){//assumes a,b sorted by finish time
    return b.hh < a.ehh || (b.hh == a.ehh amp;amp; b.mm < a.emm);
}

int eventScheduler(Event* Array, int N){
    if(N==0)return 0;
    std::sort(Array,Array N,[](Event a,Event b){
        return a.ehh < b.ehh || (a.ehh == b.ehh amp;amp; a.emm < b.emm);
    });

    int result=1;
    Event lastChosen= Array[0];
    for(int i=1;i < N;i  ){
        if(!overlapping(lastChosen,Array[i])){
            result  ;
            lastChosen=Array[i];
        }
    }
    return resu<
}

  

Интуиция, почему это работает: если мы выбрали первое событие массива, все события, которые стало невозможно выбрать, содержат время завершения первого события, поэтому нет возможности выбрать более одного события из этого подмножества. Выбор первого события минимизирует время завершения, позволяя запланировать больше событий. После отбрасывания этих событий мы находимся в том же состоянии, в котором мы начали.