1975 . 即時工作排程系統（Scheduler）
TopCoder
Description
Skynet Cyberdyne Corp. 設計了一台有上萬個處理器的超級電腦，這部電腦需要一個排程系統來將大量的即時性工作分配給不同的處理器來執行。
所謂的即時性工作，指的是一個工作會有指定的處理時段：以「開始時間$ s_i$」和「結束時間$ e_i$」來表示。例如：如果有個工作的開始時間與結束時間分別是 7 與 14，這表示該工作需要有一顆處理器由時間點 7 開始 (含時間點 7) 處理它一直到時間點 14 (含時間點 14)。
一個即時性工作只能分配給一個處理器。每個處理器在每個時間點都只能處理一個工作，所以處理時間沒有重疊的工作才可以分配給同一個處理器來執行。例如，假設現在有三個工作 A、B、C，它們的「開始時間」和「結束時間」如下表所示：
| 工作 | 開始時間 | 結束時間 | 工作類型 |
| A | 3 | 5 | 即時 |
| B | 1 | 3 | 即時 |
| C | 7 | 9 | 即時 |
在這個例子裏，我們可以將工作 A 和 C 分配給一顆處理器，然後將工作 B 分配給另一顆處理器，用兩顆處理器就可以完成這三件工作。請注意，工作 A 和 B 不能分配給同一顆處理器，因為它們在時間點 3 重疊。
除了即時性工作以外，另外一種常見的工作我們稱為「非即時性工作」：以「工作長度$w_i$」和「完成時限$ d_i$」來表示。其中「工作長度」是指這件工作至少要花費單顆處理器多少個時間點；而「完成時限」指的是這件工作最晚必須在哪一個時間點完成。一件非即時性工作同一個時間點儘能選擇一個處理器來執行。不過，與即時性工作不同的是，一件非即時性工作可以在任意時間點暫停、甚至可以更換處理器並且繼續執行（我們假設它不耗費任何時間）。
讓我們來看另一個例子：假設現在有三件工作 D、E、F，它們的參數如下：
| 工作 | 工作類型 | ||
| D | $s_D=2$ | $e_D=5$ | 即時 |
| E | $w_E=3$ | $d_E=6$ | 非即時 |
| F | $w_F=4$ | $d_F=6$ | 非即時 |
那麼使用兩顆處理器可以順利完成所有工作：第一顆在前 6 個時間點分別執行：E, D, D, D, D, E；第二顆在前 6 個時間點分別執行：F, E, F, F, F, X(休息)。
請完成一個程式，計算一批工作最少需要用到幾個處理器。
Input Format
第一行有一個非負整數 n，代表即時性工作的數目。下面接著 n 行，每一行有兩個正整數$ s_i $和$ e_i$（$s_i\leq e_i$），分別代表一件即時性工作的「開始時間」和「結束時間」，兩數字間至少以一個空白隔開。接下來有一個非負整數 m，代表非即時性工作的數目。緊接著的 m 行，每一行有兩個正整數$ w_i $和$ d_i$（$w_i\leq d_i$），分別代表一件非即時性工作的「工作長度」和「完成時限」。
時間點皆由 1 開始計算。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~3) | $n\leq 10^ 3; m=0; s_i, e_i\leq 100$ | 15 |
| 2 (0~7) | $n\leq 10^ 5; m=0; s_i, e_i\leq 10^ 6$ | 28 |
| 3 (8~11) | $n=0; m\leq 10^ 5; w_i, d_i\leq 10^ 6$ | 9 |
| 4 (12~15) | $n, m\leq 10^ 3; s_i,e_i,w_i, d_i\leq 10^ 6$ | 11 |
| 5 (0~19) | $n, m\leq 10^ 5; s_i,e_i,w_i, d_i\leq 10^ 6$ | 37 |
Output Format
輸出一行，只包含一個數字，代表最少需要使用到的處理器個數。
Sample Input 1
3 5
1 3
7 9
0
Sample Output 1
Sample Input 2
1 5
2 3
2 6
6 12
4 11
6 9
10 14
11 15
15 17
14 20
0
Sample Output 2
Hints
Problem Source
題目取自2017 TOI選訓第三次模擬考pA
Problem set by Yihda Yol
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~3 | 15 |
| 2 | 0~7 | 28 |
| 3 | 8~11 | 9 |
| 4 | 12~15 | 11 |
| 5 | 0~19 | 37 |