Girls and the Boxes
Problem
You are given \(n\) boxes and each box contains two small boxes of Red and Blue color. The size of the Red and Blue colored boxes are \(b_i\) and \(r_i\) respectively.
Consider a sequence of distinct integers \(x_1, x_2, \ldots, x_k\ (1 \le x_i \le n)\).
Consider \(x\) to be a suitable sequence if, for every \(1 \le i < k\ holds\ b_{x_i} < r_{x_{i+1}}\ and\ r_{x_i} < b_{x_{i+1}}\).
Determine the maximum possible size of the suitable sequence.
Input format
- First line: \(n\) representing the number of available boxes \((1 \leq n \leq 5 \cdot 10^5)\)
- Next \(n\) lines: Two positive integers \(r_i\) and \(b_i\) \((1\leq r_i,\ b_i \leq 10^9)\)
Output format
Print only one integer representing the size of the maximum suitable sequence.
Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation
sequence $$[1,3]$$ is suitable since $$b_1 < r_3$$ and $$r_1 < b_3$$. Its size is 2 and it can be shown that we can't arrange all 3 girls to form a suitable sequence of size \(3\).
