D. The Union of k-Segments

sorting, overlap

출처: Codeforces D. The Union of k-Segments

SOL)

열리는 이벤트와 닫히는 이벤트를 두고

정들을 다 정렬한다.

위치가 같을때 열리는 이벤트가 앞에 있도록

open = -1, close = 1로 둔다.

열릴때는 cnt값을 1증가시키고 닫힐때는 -1감소시켜

답을 채워나가면 된다.

[-] Collapse

#include<stdio.h>
#include<vector>
#include<algorithm>
#define mp make_pair
const int N = 200010;

using namespace std;

int n, k;
int cnt, s;
vector<pair<int, int> > ans;
vector<pair<int, int> > events;

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d %d", &n, &k);

    for (int i = 0; i < n; i++){
        int s, e; scanf("%d %d", &s, &e);
        events.push_back(mp(s, -1));
        events.push_back(mp(e, 1));
    }
    sort(events.begin(), events.end());
    for (int i = 0; i < events.size(); i++){
        if (events[i].second == -1 && cnt == k - 1)
            s = events[i].first;
        else if (events[i].second == 1 && cnt == k)
            ans.push_back(mp(s, events[i].first));

        cnt -= events[i].second;
    }

    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++){
        printf("%d %d\n", ans[i].first, ans[i].second);
    }

    return 0;
}