1603 問題 F: 藍(lán)橋杯算法訓(xùn)練VIP-會(huì)議中心
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 87 解決: 9
題目描述
Siruseri政府建造了一座新的會(huì)議中心。許多公司對(duì)租借會(huì)議中心的會(huì)堂很感興趣，他們希望能夠在里面舉行會(huì)議。
對(duì)于一個(gè)客戶而言，僅當(dāng)在開會(huì)時(shí)能夠獨(dú)自占用整個(gè)會(huì)堂，他才會(huì)租借會(huì)堂。會(huì)議中心的銷售主管認(rèn)為：最好的策略應(yīng)該是將會(huì)堂租借給盡可能多的客戶。顯然，有可能存在不止一種滿足要求的策略。
例如下面的例子。總共有4個(gè)公司。他們對(duì)租借會(huì)堂發(fā)出了請(qǐng)求，并提出了他們所需占用會(huì)堂的起止日期（如下表所示）。
開始日期 結(jié)束日期
公司1 4 9
公司2 9 11
公司3 13 19
公司4 10 17
上例中，最多將會(huì)堂租借給兩家公司。租借策略分別是租給公司1和公司3，或是公司2和公司3，也可以是公司1和公司4。注意會(huì)議中心一天最多租借給一個(gè)公司，所以公司1和公司2不能同時(shí)租借會(huì)議中心，因?yàn)樗麄冊(cè)诘诰盘熘睾狭恕?
銷售主管為了公平起見，決定按照如下的程序來確定選擇何種租借策略：首先，將租借給客戶數(shù)量最多的策略作為候選，將所有的公司按照他們發(fā)出請(qǐng)求的順序編號(hào)。對(duì)于候選策略，將策略中的每家公司的編號(hào)按升序排列。最后，選出其中字典序最小[1]的候選策略作為最終的策略。
例中，會(huì)堂最終將被租借給公司1和公司3：3個(gè)候選策略是{(1,3),(2,3),(1,4)}。而在字典序中(1,3)< (1,4)< (2,3)。
你的任務(wù)是幫助銷售主管確定應(yīng)該將會(huì)堂租借給哪些公司。
輸入
輸入的第一行有一個(gè)整數(shù)N，表示發(fā)出租借會(huì)堂申請(qǐng)的公司的個(gè)數(shù)。第2到第N+1行每行有2個(gè)整數(shù)。第i+1行的整數(shù)表示第i家公司申請(qǐng)租借的起始和終止日期。對(duì)于每個(gè)公司的申請(qǐng)，起始日期為不小于1的整數(shù)，終止日期為不大于109的整數(shù)。
數(shù)據(jù)規(guī)模和約定
在所有輸入中，N≤200000。
[1] 字典序指在字典中排列的順序，如果序列l(wèi)1是序列l(wèi)2的前綴，或者對(duì)于l1和l2的第一個(gè)不同位置j，l1[j]< l2[j]，則l1比l2小。
輸出
輸出的第一行應(yīng)有一個(gè)整數(shù)M，表示最多可以租借給多少家公司。第二行應(yīng)列出M個(gè)數(shù)，表示最終將會(huì)堂租借給哪些公司。
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情