2911번: 전화 복구

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


$O(nlg n)$

쉽게 생각하기 위해 (p,c) 히스토그램을 그려보자.
전화수를 최소로 하기 위해 y값이 같고 붙어있는 칸을 같이 묶어보면 답은 이 묶음 수가 된다는 것을 직관적으로 알 수 있다.
이것을 구하는 방법은 매우 쉬운데, ci-c(i-1)이 양수인 경우를 누적한 합이 된다.

#include<stdio.h>
#include<algorithm>
#define f first
#define s second
using namespace std;
typedef long long ll;
const int MAX_N = 1e5;
pair<int, int> p[MAX_N];
int n, m;
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d %d", &p[i].f, &p[i].s);
    sort(p, p + n);
    ll res = p[0].second;
    for (int i = 1; i < n; i++) res += max(p[i].s - p[i - 1].s, 0);
    printf("%lld", res);
    return 0;
}