O(N*LogN)算法存在以下问题

Question

有以下问题:

一个城市中最负盛名的体育俱乐部拥有N个成员.每个成员都很强大而且漂亮.更准确地说,我这个俱乐部的成员(成员在他们进入俱乐部时编号)具有力量S _i和美女B _i.由于这是一个非常有声望的俱乐部,它的成员非常富有,因而非凡的人,所以他们经常非常讨厌彼此.严格地说,我第球杆X先生的构件讨厌Ĵ第球杆ÿ先生的构件若S _我 ≤小号_Ĵ和B _我 ≥乙_Ĵ或若S _我 ≥小号_Ĵ和B _我 ≤乙_Ĵ(如果两个X先生的财产比Y先生的相应财产要大,他甚至没有注意到他,另一方面,如果他的两个财产都少,他非常尊重Y先生.

为了庆祝新的2003年,俱乐部的管理部门正计划组织一个派对.然而,他们担心,如果两个互相仇恨的人同时参加聚会,喝了一两杯他们就会开始打架.所以不应该邀请两个互相仇恨的人.另一方面,为了将俱乐部的声望保持在适当的水平,政府希望邀请尽可能多的人.

作为唯一一个不怕触摸电脑的政府,你要编写一个程序,找出邀请参加聚会的人.

输入

*输入文件的第一行包含整数N - 俱乐部的成员数.(2≤N≤100,000).下一个N行包含每两个数字- S _我和B _我分别(1个≤小号_我,B _我.≤109)*

产量

在输出文件的第一行打印可以邀请参加聚会的最大人数.在第二行输出N个整数 - 以任意顺序邀请的成员数.如果存在多个解决方案,则输出任何一个

样品测试

输入

  4
  1 1
  1 2
  2 1
  2 2

产量

  2
  1 4

我试图解决一个问题但我的算法的复杂性是O(N ^ 2),并且因为2 <= N <= 100000,所以需要改进算法.我正在使用具有O(N ^ 2)复杂度的最长增加的子序列动态编程算法来解决该问题.有人知道如何改进算法吗？

Answer 1

两个实力和美貌相同的人互相讨厌，而且实力和美貌的界限很紧\xe2\x80\xa6

\n