Maximum Independent Subset

View as PDF

Submit solution

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

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 [L_i, R_i]. 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 L_i and R_i, representing that S contains all integers in the range [L_i, R_i].

Output Specification

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


1 \le N \le 10^5

1 \le L_i \le R_i \le 10^{18}

For all pairs (i, j) such that i \neq j, either L_i > R_j or L_j > R_i.

Subtask 1 [10%]

1 \le L_i \le R_i \le 20

Subtask 2 [20%]

L_i = R_i

Subtask 3 [30%]

1 \le N \le 2000

1 \le L_i \le R_i \le 10^{12}

Subtask 4 [40%]

No further constraints.

Sample Input

5 7
9 11
1 3

Sample Output



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\}.


There are no comments at the moment.