0

我的问题是，我们得到了一份活动列表以及开始和结束时间，然后我们必须找出我们可以做的最大活动。这个问题很常见，我已经应用了一种贪婪的方法，但是我的代码中出现了运行时分段错误，所以我将它发布在下面。

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

请帮助！提前谢谢！！

4

1 回答 1

0

在你最后的迭代中

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

你可能迭代一个过去的大小events

原因是，当您通过possible_events++以前使用的访问元素时possible_events，该变量的值在访问之后会像以前一样大（因为 post-fix ++），因此如果您在每次迭代中调用评估，则值ofpossible_events将number_of_events+1在循环结束后

您需要迭代到少一个：

for(iter=0;iter<possible_events-1;iter++)
于 2012-05-26T12:54:21.630 回答