먹이사슬
문제
1부터 N까지 번호가 붙여져 있는 N마리 서로 다른 동물이 있다.
모든 동물은 동일한 하나의 수평선 상에서 연속된 구간 내에서 활동한다. 이 구간을 그 동물의 활동영역이라 한다.
동물의 활동영역은 구간의 왼쪽 위치와 오른쪽 위치 쌍으로 나타낸다.
예를 들어, 7마리 동물의 활동영역이 다음 그림과 같다고 하자. 각 동물의 활동 영역은 선분으로 나타내어져 있다.
아래에서 동물 1의 활동영역은 (2, 4), 동물 2의 활동영역은 (6, 10), ..., 동물 7의 활동영역은 (3, 4)이다.
활동영역이 (x1, x2)인 동물 i와 (x3, x4)인 동물 j에 대하여, 다음 세 조건 중 하나를 만족하면 i가 j보다 먹이사슬에서 상위에 있다고 한다.
조건 1: x1 < x3 이고 x2 > x4
조건 2: x1 = x3 이고 x2 > x4
조건 3: x1 < x3 이고 x2 = x4
동물들의 집단에 대하여 다음 조건을 만족하면서 모든 동물들을 나열 할 수 있으면, 이 집단은 먹이사슬 구조를 가진다고 말한다.
조건: 나열된 각 동물은 뒤에 나오는 모든 동물보다 먹이사슬에서 상위에 있다.
단, 하나의 동물로 이루어진 집단도 먹이사슬 구조를 가진다고 말한다.
먹이사슬 구조를 가지는 동물 집단의 크기는 이 집단에 속하는 동물의 수로 정의한다.
동물들의 활동영역이 주어질 때, 먹이사슬 구조를 가지는 동물 집단의 최대 크기를 구하는 프로그램을 작성하시오.
앞의 그림 예에서 먹이사슬 구조를 가지는 동물 집단의 예로 {1}, {2, 4}, {2, 6}, {1, 3}, {1, 3, 7}, ... 등이 있다.
집단 {1, 3, 7}에서 3은 1보다 상위이고 1은 7보다 상위로서 먹이사슬 구조를 가지는 최대 크기의 집단이다.
최대 크기 집단은 하나 이상일 수 있다.
입력형식
입력의 첫 번째 줄에는 동물의 수를 나타내는 N(1≤N≤500,000)이 주어진다.
다음 각 줄에 동물의 번호, 동물의 활동영역의 왼쪽 위치 L, 오른쪽 위치 R이 빈 칸을 사이에 두고 나온다.
L, R은 1 이상 1,000,000,000 이하의 양의 정수이다.
<제약 조건>
• N이 20이하인 테스트데이터가 전체의 20%이다.
• 다음 조건을 만족하는 테스트데이터가 전체의 70%이다.
모든 두 동물의 활동영역은 서로 겹치지 않거나, 겹친다면 먹이사슬에서 하나가 나머지 하나의 상위 관계에 있다.
출력형식
입력 예
7
1 2 4
3 1 5
4 7 8
6 9 10
2 6 10
5 5 7
7 3 4
출력 예
3
소스코드
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define MAX_N 500000
#define MAX_S 1000000000
struct SE {
int s, e;
int num;
} se[MAX_N];
int n;
int du[MAX_N], dh;
int cmp(const void* a, const void* b)
{
SE A = *(SE *)a;
SE B = *(SE *)b;
if (A.s == B.s)
return B.e - A.e;
return A.s - B.s;
}
void ins_du(int x)
{
if (dh == 0 || du[dh - 1] >= x)
{
du[dh++] = x;
return;
}
int s, e;
s = 0;
e = dh - 1;
while (s <= e)
{
int m = (s + e) / 2;
if (du[m] >= x)
s = m + 1;
else
e = m - 1;
}
du[e + 1] = x;
}
int main()
{
scanf("%d", &n);
assert(1 <=n && n <= MAX_N);
int i;
for (i = 0; i < n; i++)
{
scanf("%d %d %d", &se[i].num, &se[i].s, &se[i].e);
assert(1 <= se[i].s && se[i].s < se[i].e&& se[i].e <= MAX_S);
}
qsort(se, n, sizeof(SE), cmp);
int m = 1;
for (i = 1; i < n; i++)
{
if (se[i].s != se[i - 1].s || se[i].e != se[i - 1].e)
{
se[m] = se[i];
m++;
}
}
dh = 0;
for (i = 0; i < m; i++)
{
ins_du(se[i].e);
}
printf("%d\n", dh);
return 0;
}
