Выбор действия

Question

Вопрос в том, что нам дается список мероприятий с их началом и временем окончания, тогда мы должны выяснить, какие действия мы можем сделать. Вопрос довольно распространен, и я применил подход «Жадный», но я получаю код детекции в своем коде, поэтому я размещаю его ниже.

#include<stdio.h> 
typedef struct event 
{ 
    long long int start_time; 
    long long int end_time; 
    long long int event_number; 
}event; 

long long int compare(const void *x, const void *y) 
{ 
    event *e1 = (event *)x, *e2 = (event *)y; 
    return (*e1).end_time - (*e2).end_time; 
} 
/* Given the list of events, our goal is to maximise the number of events we can 
    attend. */ 
int main() 
{ 
int tests; 
scanf("%d",&tests); 
while(tests--) 
{ 
long long int number_of_events; 
//printf("enter no of activities"); 
    scanf("%lld",&number_of_events); 
    event T[number_of_events]; 
    long long int iter; 
    for(iter=0;iter<number_of_events;iter++) 
    { 
//   printf("enter start time and end time of %dth activity",iter); 
      scanf("%lld%lld",&T[iter].start_time,&T[iter].end_time); 
      T[iter].event_number = iter; 
    } 
    /* Sort the events according to their respective finish time. */ 
    qsort(T,number_of_events,sizeof(event),compare); 


    long long int events[number_of_events]; // This is used to store the event 
              // numbers that can be attended. 

    long long int possible_events = 0; // To store the number of possible events 

    //Taking the first task 
    events[possible_events++] = T[0].event_number; 
    long long int previous_event = 0; 

    /* Select the task if it is compatable with the previously selected task*/ 
    for(iter=1;iter<number_of_events;iter++) 
    { 
      if(T[iter].start_time >= T[previous_event].end_time) 
      { 
        events[possible_events++] = T[iter].event_number; 
        previous_event = iter; 
      } 
    } 
    //printf("Maximum possible events that can be attended are %d. They are\n", 
    // possible_events); 
    printf("%lld\n",possible_events); 
    /* list of selected activities 
    for(iter=0;iter<possible_events;iter++) 
    { 
      printf("%d\n",events[iter]); 
    }*/ 

} 
return 0; 
} 

Просьба помочь! Thanx заранее!

Answer 1

В вашей итерации в конце

for(iter=0;iter<possible_events;iter++) 

Вы, возможно, iteratate один мимо размера events

Причина в том, что в то время как вы доступ к элементам через possible_events++ в предыдущих использований possible_events, значение эта переменная будет больше после доступа по-прежнему (из-за постобработки ++), поэтому, если вы вызываете оценку на каждой итерации, значение possible_events будет number_of_events+1 после окончания цикла

Вы должны перебирать на единицу меньше:

for(iter=0;iter<possible_events-1;iter++)