Time limit
2s
Memory limit
128 MB
There are N axis-aligned rectangles on a coordinate plane. For each rectangle, call its lower-left vertex the start point and its upper-right vertex the end point.
You want to choose some rectangles and form a set L. For every two distinct rectangles p and q in L, one of the following conditions must hold:
Find the maximum number of rectangles that can be chosen while satisfying this condition.
The first line contains the number of rectangles N. (1 <= N <= 100,000)
Each of the next N lines contains four integers x1, y1, x2, and y2, separated by spaces, describing one rectangle. (x1, y1) is the lower-left vertex, and (x2, y2) is the upper-right vertex.
It is always true that x1 < x2 and y1 < y2, and every coordinate is between 0 and 100,000 inclusive.
Print the maximum number of rectangles that can be included in a set satisfying the condition.