최대 증가 직사각형 집합
시간 제한2초메모리 제한128 MB
N개의 직사각형이 주어질 때, 서로 대각선 방향으로 완전히 앞서는 관계로 정렬 가능한 최대 부분집합의 크기를 구하는 문제입니다.
문제
좌표평면에 축에 평행한 직사각형 N개가 있다. 각 직사각형에서 왼쪽 아래 꼭짓점을 시작점, 오른쪽 위 꼭짓점을 끝점이라고 하자.
몇 개의 직사각형을 골라 집합 L을 만들 때, L에 속한 서로 다른 두 직사각형 p, q는 항상 다음 두 조건 중 하나를 만족해야 한다.
- p의 끝점의 x좌표가 q의 시작점의 x좌표보다 작고, p의 끝점의 y좌표도 q의 시작점의 y좌표보다 작다.
- q의 끝점의 x좌표가 p의 시작점의 x좌표보다 작고, q의 끝점의 y좌표도 p의 시작점의 y좌표보다 작다.
이 조건을 만족하도록 고를 수 있는 직사각형의 최대 개수를 구하라.
입력
첫째 줄에 직사각형의 개수 N이 주어진다. (1 <= N <= 100,000)
둘째 줄부터 N개의 줄에는 각 직사각형을 나타내는 네 정수 x1, y1, x2, y2가 공백으로 구분되어 주어진다. (x1, y1)은 왼쪽 아래 꼭짓점, (x2, y2)는 오른쪽 위 꼭짓점이다.
항상 x1 < x2, y1 < y2이며, 모든 좌표는 0 이상 100,000 이하이다.
출력
조건을 만족하는 집합에 넣을 수 있는 직사각형의 최대 개수를 출력한다.