a684. CPE：Minimal coverage (UVa 10020)

題目描述

給定 x 軸上的若干線段 [Lᵢ,Rᵢ]，選出最少條線段，使它們的聯集完全覆蓋 [0,M]。線段可以超出目標區間。

輸入格式

第一行為測試資料筆數，之後有空白行。每筆先有 M（1 ≤ M ≤ 5000），接著每行一對 Lᵢ Rᵢ，|Lᵢ|、|Rᵢ| ≤ 50000，線段數最多 100000。以 0 0 結束該筆，不是可用線段。相鄰資料間有空白行。

輸出格式

若無法覆蓋，輸出 0。否則先輸出最少線段數，再逐行輸出選中的線段端點，必須依左端點 Lᵢ 由小到大排列。若有多組最優解，任一組均符合原題要求。相鄰測試資料輸出間印一個空白行。

原題：https://onlinejudge.org/external/100/10020.pdf

本平台測資說明

本平台目前採固定答案比對；本批測資僅選用最優線段集合唯一且左端點互異的案例，新增多解測資時需配置特殊判題器。