a352. TOI 2019/03 潛力組：教室配置

題目描述

資工系預計開設 N 門課，每門課有開始時間與結束時間，且上課時需要一間教室。系上原本已有一間教室，可以視需要增建。

時間不重疊的課程可以共用教室。若一門課的結束時間不晚於另一門課的開始時間，兩門課就能使用同一間教室。

請求出能安排全部課程時，系上最少會有幾間教室。要求的是包含原有教室在內的總數，而非增建數。

輸入格式

第一行為整數 N，表示課程數。接下來 N 行，每行有兩個整數 S、E，表示一門課的開始時間與結束時間。

• 0 ≤ N ≤ 10⁷
• 0 ≤ S < E ≤ 10⁷ − 1

原題分組：10 分資料 N ≤ 10；30 分資料 N ≤ 10⁴；其餘 60 分使用完整限制。

輸出格式

輸出一個整數 K，表示系上最少會有的教室總數。

來源

TOI 2019 年 3 月潛力組〈教室配置〉。依官方原題重新撰寫。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/201903/A1-Classroom(Q).pdf