私の質問は、開始時刻と終了時刻が記載されたアクティビティのリストが与えられた後、実行できる最大のアクティビティを見つけなければならないということです。質問はかなり一般的で、貪欲なアプローチを適用しましたが、コードでランタイムセグメンテーション エラーが発生しているため、以下に投稿しています。
#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;
}
よろしくお願いします!! 事前にサンクス!!