[BaekJoon][2532] 먹이사슬

BAEKJOON ONLINE JUDGE

한국정보올림피아드 시.도 지역본선 2012

2532 먹이사슬

https://www.acmicpc.net/problem/2532

1. 정렬

선의 왼쪽 시작지점을 기준으로 정렬한다.

왼쪽 시작지점은 오름차순으로, 왼쪽 시작지점이 같을 경우에는 오른쪽 끝 지점이 작은순으로 (내림차순)으로 정렬한다.

2. 문제의 조건을 보면 같은 시작점, 같은 끝점을 지는 선분은 포함하지 않는다. 하지만 입력으로 들어올 수 있기 때문에 이를 무시해 준다.

3. LIS (최장 길이 증가 부분 수열 Longest Increasing Subsequence)

정렬한 값을 순서대로 LIS O(NlogN)을 구현한다. O(N^2)은 time limit난다.

LIS (O(NlogN))은 이진탐색을 이용하여 구현한다.

#include <cstdio>
#include <algorithm>
using namespace std;
 
#define MaxN    500000
 
struct Data {
    int start, end;
    int idx;
}d[MaxN];
 
int n, m;
int lis[MaxN];
 
void input()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &d[i].idx, &d[i].start, &d[i].end);
    }
}
 
bool cmp(const Data &first, const Data &second)
{
    if (first.start == second.start)    return first.end > second.end;
    return first.start < second.start;
}
 
void sort()
{
    sort(d, d + n, cmp);
}
 
void eraseSame()
{
    m = 1;
    for (int i = 1; i < n; i++) {
        if (!(d[i].start == d[i - 1].start && d[i].end == d[i - 1].end)) {
            d[m++] = d[i];
        }
    }
}
 
void process()
{
    // 끝값을 이용하여 최장길이 감소 수열 만들기
    int ans = 1;
 
    lis[0] = d[0].end;
 
    for (int i = 1; i < m; i++) {
 
        if (d[i].end <= lis[ans - 1]) {
            lis[ans++] = d[i].end;
            continue;
        }
 
        int s = 0, e = ans - 1;
        while (e >= 0 && s <= e) {
            int middle = (s + e) / 2;
            if (lis[middle] >= d[i].end)    s = middle + 1;
            else e = middle - 1;
        }
 
        lis[e + 1] = d[i].end;
    }
 
    printf("%d\n", ans);
}
 
int main()
{
    input();
    
    sort();
 
    eraseSame();
 
    process();
 
    return 0;
}