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

49愛的鼓勵 6訂閱站台

A computer program stores the values of its variables in memory. For arithmetic computations, the values must be stored in easily accessed locations called registers. Registers are expensive such that we need to use them efficiently. If two variables are never used simultaneously, then we can allocate them to the same register. Suppose that there are n variables used in a computer program. For convenience, we use Var = {1, 2,..., n} to represent these n variables. For each variable i, we know the start time s_i and the finish time f_i when it is used. A variable i is active during the time interval [s_i, f_i], where s_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 if the corresponding time intervals are disjoint, that is, [s_i, f_i] [s_j, f_j] = . Note that even when s_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 variables and the corresponding start time and finish time, your task is to write a computer program to compute the minimum number of used registers.

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

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 the required 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 the number of test cases to follow. For each test case, the set of registers Var = {1, 2,..., n} is given with the following format: The first line of each test case contains a positive integer n. In the following n lines, each line contains two positive integers separated by a single space. The first integer represents the start time and the second integer represents 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 required registers.

Sample Input 

2
8
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
6
1 2
2 3
3 4
4 5
5 6
6 7

Sample Output 

1
2

---

求並行執行最大數, 使用 priority_queue

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct var {
    int s, f;
};
struct cmp2 {
    bool operator() (int x, int y) {
        return x - y > 0;
    }
};
bool cmp(var i, var j) {
    if(i.s != j.s)
        return i.s - j.s < 0;
    return i.f - j.f < 0;
}
int main() {
    int t, n, i;
    var V[10000];
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++) {
            scanf("%d %d", &V[i].s, &V[i].f);
        }
        sort(V, V+n, cmp);
        priority_queue<int, vector<int>, cmp2> pQ;
        int ans = 0, end;
        for(i = 0; i < n; i++) {
            while(!pQ.empty()) {
                end = pQ.top();
                if(end < V[i].s) {
                    pQ.pop();
                } else {
                    break;
                }
            }
            pQ.push(V[i].f);
            if(pQ.size() > ans)
                ans = pQ.size();
        }
        printf("%d\n", ans);
    }
    return 0;
}