a500:
外送接單 (Delivery)
內容
美味廚房是一家販售平價料理的知名餐廳，由老闆小郭獨自一人經營。
近期小郭發現與外送服務平台合作可以減少人力支出並增加利潤，故決定將營業型態轉為僅提供外送接單服務。然而大量的訂單使得小郭應接不暇，為了維護餐點品質，小郭決定在自己能夠負荷的範圍內選擇性地接受訂單。
我們用數對 (p, t) 來代表一筆訂單，其中 p 是準備該筆訂單所須的時間，t是該筆訂單必須完成的時間點。
每天小郭會從第 0 個時間點開始準備餐點，小郭在完成一筆訂單後才能開始準備另一筆訂單，中間轉換的時間可以忽略。
假設今天有三筆訂單 (3, 4)、(2, 3)、(3, 5)，小郭可以在時間範圍 [0, 3] 或時間範圍 [1, 4] 準備 1 號訂單，但這麼一來小郭就無法再接受其他訂單了。
小郭也可以在時間範圍 [0, 2] 準備2號訂單，接著在時間範圍 [2, 5] 準備3號訂單，如此一來小郭便能接受2筆訂單。
給定所有訂單的資料，請幫忙計算小郭最多可以接受多少筆訂單。
輸入說明
第一列有一個整數N (1 ≤ N ≤ 105)，代表總共收到了幾筆訂單。
接下來有N列，每一列有兩個整數P以及T (1 ≤ P ≤ 109, 1 ≤ T ≤ 109 )，代表一筆訂單需要連續準備P單位時間並在時間點T以前完成。
輸出說明
請輸出一個數字，代表最多可以接受的訂單數量。
範例輸入
#1
3 3 4 2 3 3 5
範例輸出
#1
2
範例輸入
#2
8 2 19 5 15 10 11 3 19 8 14 6 7 5 16 2 10
範例輸出
#2
5
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (25%): 1.0s , <1K
公開 測資點#1 (25%): 1.0s , <1K
公開 測資點#2 (25%): 1.0s , <1K
公開 測資點#3 (25%): 1.0s , <1K
公開 測資點#0 (25%): 1.0s , <1K
公開 測資點#1 (25%): 1.0s , <1K
公開 測資點#2 (25%): 1.0s , <1K
公開 測資點#3 (25%): 1.0s , <1K
提示 ：
輸入範例2的說明：
一種可能的方案是在時間點 [0, 2] 製作8號訂單，在 [2, 7] 製作2號訂單，在 [7, 12] 製作7號訂單，在 [12, 14] 製作1號訂單，最後在 [14, 17] 製作4號訂單，共接受5筆訂單；小郭無論如何都沒有辦法如期完成6筆訂單。
標籤:
出處:
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 115 | a500 | 30 | 2024-10-23 22:17 |