a337. TOI 2024/06 潛力組：會議室租用

題目描述

一間會議室有 N 位客戶申請租用。第 i 位客戶希望使用從 a_i 到 b_i 的時段，兩個端點都包含在內，並支付 c_i 元。你可以選擇接受其中一些客戶，但接受的租用時段不能互相重疊。請計算可以獲得的最大總收入。

輸入格式

第一行為正整數 N，1 ≤ N ≤ 2×10^5。

接著 N 行，每行為三個正整數 a_i、b_i、c_i，以空白分隔，表示租用起始時段、結束時段及費用。

• 1 ≤ a_i ≤ b_i ≤ 10^6
• 1 ≤ c_i ≤ 10^4

原題分組限制：20 分：N ≤ 10。20 分：所有 c_i = 1。30 分：N ≤ 10^3。30 分：無額外限制。

輸出格式

輸出一個非負整數，表示最大總收入。

範例 1

輸入：

3
1 4 6
2 7 8
5 6 3

輸出：

9

範例 2

輸入：

3
1 4 6
2 7 3
5 6 10

輸出：

16

範例 3

輸入：

3
1 4 1
2 7 1
5 6 1

輸出：

2

來源

TOI 2024 年 6 月歷屆題〈會議室租用〉，依官方 PDF 重新整理。

官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202406/MeetingRoom.pdf

標籤：TOI 歷屆