Solution Idea

50030. Activity Selection (special judge)

題目概要

經典貪心算法 - 活動選擇問題

有 $n$ 個活動,每個活動 $A_i$ 起始時間 $s_i$、結束時間 $e_i$ ($s_i \lt e_i$),現在只有一個場地,請挑選最多的活動舉辦,並且他們彼此之間不重疊時間,若 $A_i$ 與 $A_j$ 重疊,則滿足 $\textit{max}(A_{i}.\textit{start}, A_{j}.\textit{start}) \lt \textit{min}(A_{i}.\textit{end}, A_{j}.\textit{end})$。

只需要針對結束時間由小排到大,依序挑選可進行的活動即可,請維護上一個活動的結束時間!

參考解答

Ver. 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include "activity.h"
 
#include <stdio.h>
#include <stdlib.h>
 
static int cmp(const void *x, const void *y) {
    Activity *a = (Activity *) x;
    Activity *b = (Activity *) y;
    if (a->end < b->end)
        return -1;
    if (a->end > b->end)
        return 1;
    return 0;
}
int select(Activity A[], int n) {
    if (n == 0)    return 0;
    qsort(A, n, sizeof(Activity), cmp);
    int ret = 0, r = A[0].start;
 
    for (int i = 0; i < n; i++) {
        if (A[i].start >= r) {
#ifdef PRINT
            printf("%d %d\n", A[i].start, A[i].end);
#endif           
            r = A[i].end, ret++;
        }
    }
    return ret;
}

Ver. 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include "activity.h"
 
#include <stdio.h>
#include <stdlib.h>
 
static int cmp(const void *x, const void *y) {
    Activity *a = (Activity *) x;
    Activity *b = (Activity *) y;
    if (a->end < b->end)
        return -1;
    if (a->end > b->end)
        return 1;
    return 0;
}
int select(Activity A[], int n) {
    if (n == 0)    return 0;
    qsort(A, n, sizeof(Activity), cmp);
    int ret = 0, r = A[0].start;
 
    for (int i = 0; i < n; i++) {
        if (A[i].start >= r) {
#if defined PRINT
            printf("%d %d\n", A[i].start, A[i].end);
#endif           
            r = A[i].end, ret++;
        }
    }
    return ret;
}

Discussion