Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

A computer program stores the values of its variables in memory.For arithmetic computations, the values must be stored in easilyaccessed locations called registers. Registers areexpensive such that we need to use them efficiently. If twovariables are never used simultaneously, then we can allocate themto the same register. Suppose that there are n variables used ina computer program. For convenience, we useVar = {1, 2,..., n} to represent these n variables.For each variable i, we know the start time s_i andthe finish time f_i when it is used. A variable i isactive during the time interval [s_i, f_i], wheres_i and f_i are two positive integers with s_i < f_i.Two variables i and j can be stored in the same register ifthe corresponding time intervals are disjoint, that is,[s_i, f_i] [s_j, f_j] = . Note that even whens_i < f_i = s_j < f_j, the intervals [s_i, f_i] and[s_j, f_j] are not disjoint. Thus, such variables i and j cannot be placed in the same register. Given a set of n variablesand the corresponding start time and finish time, your task is towrite a computer program to compute the minimum number of usedregisters.

For example, consider Var = {1, 2, 3, 4, 5, 6, 7, 8} and thefollowing table shows the start time and finish time for eachvariable.

Note that variables {1, 3, 6} can be stored in Register A;variables {2, 5, 7} can be stored in Register B; and variables{4, 8} can be stored in Register C. The minimum number of therequired registers equals 3.

Technical Specification

• 1 n 10000.

• For each variable i, 1s_i10000 and 2f_i30000.

Input 

The first line of the input file contains an integer, denoting thenumber of test cases to follow. For each test case, the set ofregisters Var = {1, 2,..., n} is given with thefollowing format: The first line of each test case contains apositive integer n. In the following n lines, each linecontains two positive integers separated by a single space. Thefirst integer represents the start time and the second integerrepresents the finish time.The two positive integers in the i-th line of each test case represent s_i and f_i of variable i.

Output 

For each test case, output the minimum number of the requiredregisters.

Sample Input 

281 23 45 67 89 1011 1213 1415 1661 22 33 44 55 66 7

Sample Output 

12

---

簡單得說, 找最少 LIS 覆蓋整個數列

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int st, ed;
}Work;
Work Job[10000];
int cmp(const void *i, const void *j) {
    Work *x, *y;
    x = (Work *)i, y = (Work *)j;
    if(x->st != y->st)
        return x->st - y->st;
    return x->ed - y->ed;
}
int main() {
    int t, n, i, j;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        int ans = 0, tn = n;
        for(i = 0; i < n; i++)
            scanf("%d %d", &Job[i].st, &Job[i].ed);
        qsort(Job, n, sizeof(Work), cmp);

        while(tn) {
            int led = -1;
            for(i = 0, j = 0; i < tn; i++) {
                if(led < Job[i].st) {
                    led = Job[i].ed;
                } else {
                    Job[j++] = Job[i];
                }
            }
            ans ++;
            tn = j;
        }
        printf("%d\n", ans);
    }
    return 0;
}