题目描述 Description

Siruseri 政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很 感兴趣,他们希望能够在里面举行会议。

对于一个客户而言,仅当在开会时能够独自占用整个会堂,他才会租借会堂。

会议中心的销售主管认为:最好的策略应该是将会堂租借给尽可能多的客户。显 然,有可能存在不止一种满足要求的策略。

例如下面的例子。

总共有4 个公司。他们对租借会堂发出了请求,并提出了 他们所需占用会堂的起止日期(如下表所示)。

开始日期结束日期

公司1 4 9
公司2 9 11
公司3 13 19
公司4 10 17

上例中,最多将会堂租借给两家公司。租借策略分别是租给公司1 和公司3, 或是公司2 和公司3,也可以是公司1 和公司4。注意会议中心一天最多租借给 一个公司,所以公司1 和公司2 不能同时租借会议中心,因为他们在第九天重合 了。

销售主管为了公平起见,决定按照如下的程序来确定选择何种租借策略:首 先,将租借给客户数量最多的策略作为候选,将所有的公司按照他们发出请求的 顺序编号。对于候选策略,将策略中的每家公司的编号按升序排列。最后,选出 其中字典序最小1的候选策略作为最终的策略。

例中, 会堂最终将被租借给公司1 和公司3 :

3 个候选策略是 {(1,3),(2,3),(1,4)}。而在字典序中(1,3)<(1,4)<(2,3)。

你的任务是帮助销售主管确定应该将会堂租借给哪些公司。

输入描述 Input Description

输入的第一行有一个整数N,表示发出租借会堂申请的公司的个数。第2 到 第N+1 行每行有2 个整数。第i+1 行的整数表示第i 家公司申请租借的起始和终 止日期。对于每个公司的申请,起始日期为不小于1 的整数,终止日期为不大于 109 的整数。

输出描述 Output Description

输出的第一行应有一个整数M,表示最多可以租借给多少家公司。第二行应列出M 个数,表示最终将会堂租借给哪些公司。

样例输入 Sample Input

4
4 9
9 11
13 19
10 17

样例输出 Sample Output

2
1 3

数据范围及提示 Data Size & Hint

对于50%的输入,N≤3000。在所有输入中,N≤200000。

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055

asked 04 Mar '15, 22:17

%E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image

原野之狼
1.9k9399116


这种高大上的题目现在已经力不从心了。

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
permanent link

answered 21 Apr '15, 08:53

%E4%BB%B0%E6%9C%9B%E6%98%9F%E7%A9%BA's gravatar image

仰望星空
285454651

我尝试着做了一下,可能还有些问题,没有通过全部测试用例。

(26 Apr '15, 22:00) 原野之狼 %E5%8E%9F%E9%87%8E%E4%B9%8B%E7%8B%BC's gravatar image
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link: [text](http://url.com/ "title")
  • image: ![alt](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×33
×14

question asked: 04 Mar '15, 22:17

question was seen: 3,268 times

last updated: 26 Apr '15, 22:00

powered by O*S*Q*A

粤ICP备14040061号-1