[백준] 1931번

greedy 알고리즘으로 해결하는 문제이다.

나는 end 기준으로 정렬하고 같은 끝자리면 start가 작은 순으로 정렬했고, 순서대로 붙여서 해결했다.

시간 복잡도는 O(nlogn)이 걸린다.

#include <algorithm>
#include <iostream>
#include <vector>


typedef struct node {
    int start, end, count;
}node;

int main() {
    int n;
    std::cin >> n;

    std::vector<node> nodes(n);

    for (int i = 0; i < n; i++) {
        std::cin >> nodes[i].start >> nodes[i].end;
        nodes[i].count = 1;
    }

    std::sort(nodes.begin(), nodes.end(), [](const node& lhs, const node& rhs) {
        if (lhs.end != rhs.end) {
            return lhs.end < rhs.end;
        }
        return lhs.start < rhs.start;
    });

    auto current = nodes.front(); nodes.erase(nodes.begin());

    for (auto& value : nodes) {
        if (current.start >= value.end) {
            current.start = value.start;
            current.count += value.count;
        } else if (current.end <= value.start) {
            current.end = value.end;
            current.count += value.count;
        }
    }

    std::cout << current.count << std::endl;
    return 0;
}