Maximum Independent Subset

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 1G

Author:
Problem types

You are given a set S consisting of N disjoint segments of integers. That is, S can be represented as the union of N disjoint intervals of integers [Li,Ri]. Let's call a set independent if it has the property that no element of the set is exactly 2 times another. Please find the size of the largest independent subset of S.

Input Specification

The first line will contain a single integer N.

The next N lines will each contain 2 integers Li and Ri, representing that S contains all integers in the range [Li,Ri].

Output Specification

Output one integer, the size of the largest independent subset of S.

Constraints

1N105

1LiRi1018

For all pairs (i,j) such that ij, either Li>Rj or Lj>Ri.

Subtask 1 [10%]

1LiRi20

Subtask 2 [20%]

Li=Ri

Subtask 3 [30%]

1N2000

1LiRi1012

Subtask 4 [40%]

No additional constraints.

Sample Input

Copy
3
5 7
9 11
1 3

Sample Output

Copy
6

Explanation

In this case, S={1,2,3,5,6,7,9,10,11}.

One of the largest independent subsets of S is {2,5,6,7,9,11}.


Comments

There are no comments at the moment.