O(N*LogN) algorithm for the following problem

Question

There is the following problem:

The most prestigious sports club in one city has exactly N members. Each of its members is strong and beautiful. More precisely, i-th member of this club (members being numbered by the time they entered the club) has strength S_i and beauty B_i. Since this is a very prestigious club, its members are very rich and therefore extraordinary people, so they often extremely hate each other. Strictly speaking, i-th member of the club Mr X hates j-th member of the club Mr Y if S_i ≤ S_j and B_i ≥ B_j or if S_i ≥ S_j and B_i ≤ B_j (if both properties of Mr X are greater then corresponding properties of Mr Y, he doesn't even notice him, on the other hand, if both of his properties are less, he respects Mr Y very much).

To celebrate a new 2003 year, the administration of the club is planning to organize a party. However they are afraid that if two people who hate each other would simultaneouly attend the party, after a drink or two they would start a fight. So no two people who hate each other should be invited. On the other hand, to keep the club prestige at the apropriate level, administration wants to invite as many people as possible.

Being the only one among administration who is not afraid of touching a computer, you are to write a program which would find out whom to invite to the party.

Input

*The first line of the input file contains integer N — the number of members of the club. ( 2 ≤ N ≤ 100,000 ). Next N lines contain two numbers each — S_i and B_i respectively ( 1 ≤ S_i, B_i ≤ 109 ).*

Output

On the first line of the output file print the maximum number of the people that can be invited to the party. On the second line output N integers — numbers of members to be invited in arbitrary order. If several solutions exist, output any one.

Sample test(s)

Input

  4
  1 1
  1 2
  2 1
  2 2

Output

  2
  1 4

I am trying to solve a problem but the complexity of my algorithm is O(N^2) and since 2<=N<=100000 there is a need to improve an algorithm. I was solving the problem using longest increasing subsequence dynamic programming algorithm which has O(N^2) complexity. Does anybody have an idea how to improve the algorithm?

Answer 1

I don't think your O(n^2) solution is even correct, let alone efficient. If you have something like this:

3
2 2
1 1
3 3

The answer is 3. The classical LIS algorithm would give 2 however. Did you account for this?

What you can do is sort by S_i and apply LIS in O(n log n) time on B_i. For that you can either use segment trees or a simpler algorithm involving a binary search. Let me know if you need more help with this.

The total complexity is O(n log n): sorting can be done in this time, and so can LIS.

Answer 2

Here is a O(n log(n)) answer in a reasonable amount of detail.

First sort the people by beauty ascending, strength descending. Eliminate duplicates. (Either explicitly here, or implicitly by skipping over them in the next step.)

Run through the list. As you go, maintain a balanced tree of people who are possibly on their way to being the next person in a maximal ascending chain. Each person should be stored with a length of the current chain, and a pointer to a linked list of the rest of the people in the chain. The tree should be sorted by strength.

More specifically whenever you see a new person, find the next weakest person in the tree (nobody is OK), and construct a triplet (person, length of chain, pointer to chain). Insert the person in the tree. If the next stronger person in the tree has a chain no longer than the current person, delete that person. All of these operations are O(log(n)).

When you have finished processing all of the people, the maximal record in the tree will have a person at the end of a maximal chain of people, the length of the chain, and a pointer to a linked list with the rest of the people in the chain. That is your answer, print it out.

To show you with your sample data, here is what you start with:

4
1 1
1 2
2 1
2 2

This represents:

{person: 1, beauty: 1, strength: 1}
{person: 2, beauty: 2, strength: 1}
{person: 3, beauty: 1, strength: 2}
{person: 4, beauty: 2, strength: 2}

Sort by beauty increasing, then strength decreasing (there are no duplicates) to get:

{person: 3, beauty: 1, strength: 2}
{person: 1, beauty: 1, strength: 1}
{person: 4, beauty: 2, strength: 2}
{person: 2, beauty: 2, strength: 1}

To simplify things I'll just represent the tree by a sorted set. This is not how it should be represented in memory.

After inserting person 3:

{person: 3, strength: 2, length: 1, next_person: null}

Next person 1 bumps person 3.

{person: 1, strength: 1, length: 1, next_person: null}

Then person 4 comes after person 1. (I've written the linked list as a nested data structure, in reality it should be a linked list.)

{person: 1, strength: 1, length: 1, next_person: null}
{person: 4, strength: 2, length: 2, next_person: {person: 1, next_person: null}}

Then person 2 bumps person 1.

{person: 2, strength: 1, length: 1, next_person: null}
{person: 4, strength: 2, length: 2, next_person: {person: 1, next_person: null}}

To find your answer look at the end of the tree, at person 4, points at person 1. And your answer is length 2, and then (from the best to the worst) persons 4 then 1.

Answer 3

If you think of a graph with club members as vertices and 'like' as edges (i.e. if two members do not hate each other there is an edge between the corresponding vertices), one can reformulate the problem as follows:

find the maximum subset of vertices for which there is an edge between all vertices in the subset.

In fact, a subset where all vertices have mutual edges is called a Clique or complete subgraph.

To find the maximum clique takes exponential time if one can not exploit further features of the graph (see this link). This article suggests the Bron–Kerbosch algorithm.

Drawing the members in the (S,B) plane, one can see that a 'like' edge corresponds to lines going out of a vertex in the direction between 12 and 3 o'clock and between 6 and 9 o'clock. It is easy to construct an example where such edges intersect, so it's unfortunately not a planar graph.

And unfortunately, the 'like' relationship is not transitive, i.e. if A likes B and B likes C this does not imply that A also likes C (again, this is easy to see in the (S,B) plane).