有如下问题:
某城市中最负盛名的运动俱乐部正好有N名会员。每个会员都强壮美丽。更确切地说,该俱乐部的第i个成员(按其入会时间编号)具有力量Si和美丽Bi。由于这是非常负盛名的俱乐部,其成员非常富有而且是不同凡响的人物,所以他们经常出现极端的仇恨。严格来说,如果S i ≤ Sj且B i ≥ B j或Si ≥ Sj且Bi ≤ Bj,那么俱乐部的第i个成员X先生就讨厌俱乐部的第j个成员Y先生(如果X先生的两种属性都大于Y先生的相应属性,他甚至不会注意到他,另一方面,如果他的两种属性都较小,则他非常尊重Y先生)。
为了庆祝2003年新年,该俱乐部的管理层计划组织一个派对。但是,他们担心如果同时邀请两个互相憎恨的人参加派对,在喝上一两杯后,他们会开始打架。因此,不应邀请互相憎恨的两个人。另一方面,为了保持俱乐部的声望在适当水平,管理层希望邀请尽可能多的人。
作为管理层中唯一不怕接触计算机的人,你需要编写一个程序来确定应该邀请哪些人参加派对。
输入
*输入文件的第一行包含整数N-俱乐部成员的数量(2≤N≤100,000)。下一行包含每个成员的两个数字-Si和Bi(1≤Si,Bi ≤109)。
输出
在输出文件的第一行上打印可以邀请参加聚会的最大人数。在第二行输出N个整数-要邀请的成员号码按任意顺序。如果存在多个解决方案,则输出任何一个。
示例测试
输入
4
1 1
1 2
2 1
2 2
输出
2
1 4
我试图解决一个问题,但是我的算法复杂度为O(N^2),而且由于2<=N<=100000,需要改进算法。
我正在使用最长递增子序列动态规划算法来解决这个问题,它的时间复杂度是O(N^2)。
有没有人有什么想法来改进算法?