Activity Selection (special judge)

[morris821028]

Problem Description

We are given a set of activities. Each activity has a starting time s and an ending time $e$. Both $s$ and e are positive integers and $s < e$. Two activities will not have the same starting item and the ending time. Now please select the maximum number of activities so that they do not overlap. Two activities overlap if the previous activity has an ending time larger than the starting time of the later activity.

#ifndef _ACTIVITY_H
#define _ACTIVITY_H 

typedef struct activity {
    int start;
    int end;
} Activity;

int select(Activity activities[], int n);

#endif

Your implementation should return the maximum number of non-overlapping activities as the return value. In addition, if the PRINT symbol is defined your implementation also need to print the selected activities, in ascending ending time order.

Subtasks

• 5pt. $n = 2$, and the flag PRINT is not specified.
• 10pt. $n = 3$, and the flag PRINT is not specified.
• 10pt. $n = 4$, and the flag PRINT is not specified.
• 20pt. $n$ is no more than 100, and the flag PRINT is not specified.
• 55pt. $n$ is very large so you need to use qsort, and if the the flag PRINT is specified you need to print the solutions after the number of selected activities, in ascending ending time order. If the flag PRINT is not specified then you only need to return the number of selected activities.

  Hints

First you need to sort the activities according to their ending time. Then you keep selecting the activity with the earliest ending time, then removing any activities that overlap with with the activity you just selected. You repeat the second step until no activities left.

main.c (test)

#include "activity.h"
#include <stdio.h>

#define MAXN 262144
Activity A[MAXN];
int main() {
    int n, cases = 0;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            scanf("%d %d", &A[i].start, &A[i].end);
        int ret = select(A, n);
        printf("%d\n", ret);
    }
    return 0;
}

Sample Input 1

5
1 3
3 6
7 10
2 6
7 8

Sample Output 1 (if a #define PRINT is not defined)

3

Sample Output 1 (if a #define PRINT is defined)

1 3
3 6
7 8
3

Both ${\tau{1}, \; \tau{2}, \; \tau{3}}$ and ${\tau{1}, \; \tau{2}, \; \tau{5}}$ are valid solutions. Any solution that satisfies these criteria will be accepted.

Sample Input 2

p10072-job-ex2

p10072-job-ex2 after sorting with ending time

8
0 6
1 4
3 5
3 8
4 7
5 9
6 10
8 11

Sample Output 2 (if a #define PRINT is defined)

1 4
4 7
8 11
3