2318 . 煎鍋貼
TopCoder
Tags
Description
水果王國舉行了包鍋貼大賽！經過一番廝殺，參賽者總共包好了 $N$ 個鍋貼，並且按照編號 $1 \sim N$ 排成了一排，但是直到結束他們才想到，要評分之前還要先把鍋貼煎好。
為了解決這個問題，他們準備了一些鍋子來煎，他們做了如下的要求：
- 每個鍋貼都要裝在其中一個鍋子裡
- 同一個鍋子的起鍋時間要一樣
- 鍋子必須裝著編號連續的鍋貼，例如，不能有一個鍋子恰裝著編號為 $1, 3, 4$ 的鍋貼
但是不同的鍋貼是有不同的烹調方式的，具體來說，對於編號為 $i$ 的鍋貼，他的起鍋時間必須介在 $[A_i,B_i]$ 之間才能保證美味。
鍋子很大，但是搬運鍋子很費工，所以他們希望能用最少的鍋子把所有鍋貼煎好。
現在這個問題交給了你，請你設計出一種放鍋貼的方式使用最少的鍋子。
Input Format
第一行會有一個整數 $N$，代表有幾個鍋貼，接下來的 $N$ 行，每行會有兩個整數 $A_i, B_i$，代表第 $i$ 個鍋貼的起鍋時間需要界在 $[A_i, B_i]$ 之間
對於所有測試資料：
- $1 \leq N \leq 10^ 5$
- $1 \leq A_i \leq B_i \leq 10^ 9$
Output Format
第一行請輸出一個整數 $K$，代表總共進行了幾次操作。
接下來請輸出 $K$ 行，每行包含 $3$ 個整數 $T_j, C_j, D_j$，代表第 $ j$ 個鍋子會在時間點 $T_j$ 起鍋, 並且上面有第 $[C_j, D_j]$ 個鍋貼
- $1 \leq K \leq 10^ 5$
- $1 \leq T_j \leq 10^ 9$
- $1 \leq C_j \leq D_j \leq N$
Sample Input 1
1 2
1 1
2 3
4 4
1 1
Sample Output 1
4 4 4
1 5 5
3 3 3
1 1 2
Sample Input 2
4 7
3 8
9 10
5 13
8 9
10 18
Sample Output 2
5 1 2
9 3 5
10 6 6
Hints
對於範測一，分配的結果如下，
第一個鍋子裝著第四個鍋貼，並且在時間 4 起鍋。
第二個鍋子裝著第五個鍋貼，並且在時間 1 起鍋。
第三個鍋子裝著第三個鍋貼，並且在時間 3 起鍋。
第四個鍋子裝著第一個和第二個鍋貼，並且在時間 1 起鍋。
可以看出這樣的分配滿足要求，因為
$1 = A_1 \leq 1 \leq B_1 = 2$
$1 = A_2 \leq 1 \leq B_2 = 1$
$2 = A_3 \leq 3 \leq B_3 = 3$
$4 = A_4 \leq 4 \leq B_4 = 4$
$1 = A_5 \leq 1 \leq B_5 = 1$
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~9 | $N \leq 20$ | 20 |
| 3 | 0~1, 10~19 | $B_i \leq 100$ | 37 |
| 4 | 0~29 | 無其他限制 | 43 |