백준 12832 (C++) Tickets

최초 업로드: 2025-10-25 19:59:48

최근 수정 시간: 2025-10-25 19:59:48

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] Tickets

[문제 링크](https://www.acmicpc.net/problem/12832)

## 문제 설명

The match of the year will be played next week. There are N seats in the stadium numbered by the integers 1 to N. Each fan can request one ticket and can specify the range of seats where he would be willing to sit. The range is specified by two integers F and L, the first and last seat in the range, respectively. This means that the fan accepts any seat S such that F ≤ S ≤ L holds. The ticket office has already received M requests from football fans and wants to select the maximal number of requests that can be simultaneously satisfied.

Write a program that computes the maximal number of fans that each can obtain a ticket with a suitable seat, and gives an adequate seat assignment. No two fans can get the same seat.

## 입력

The first line of the input contains two integers N (1 ≤ N ≤ 100000), the number of seats, and M (1 ≤ M ≤ 1000000), the number of requests. The seats are numbered by 1, . . . , N. Each of the next M lines contains two integers F and L (1 ≤ F ≤ L ≤ N), a request specification. Requests are identified by the numbers 1, . . . , M in the order of their appearance in the input.

## 출력

The first line of the output must contain one integer K, the maximal number of the selected requests. Each of the next K lines contains two integers S R, a seat assignment, where S is a seat number and R is the number of the request obtaining the seat S. The seat assignments can be given in any order. If there are multiple solutions, your program should output only one; it does not matter which one.

## 풀이
마지막 시간 오름차순, 처음 시간 오름차순으로 정렬하고, 가능한 시간 중 첫 시간에 매핑하였다. 첫 시간은 분리 집합으로 찾아주었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int parent[100'001], mapping[100'001];

int _find(int x) {
    if(x==parent[x]) return x;
    return parent[x] = _find(parent[x]);
}

struct element {
 int l, r, idx;
 bool operator<(const element e) const {
 if(r!=e.r) return r<e.r;
 return l<e.l;
 }
};

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m; cin >> n >> m;
 for(int i=1;i<=n;i++) parent[i]=i;

vector<element> v(m);
 for(int i=0;i<m;i++) {
 cin >> v[i].l >> v[i].r;
 v[i].idx=i+1;
 }
 sort(v.begin(), v.end());

for(auto e:v) {
 int first = _find(e.l);
 if(first<=e.r) {
 parent[first]=_find(first+1);
 mapping[first]=e.idx;
 }
 }

vector<int> res;
 for(int i=1;i<=n;i++) {
 if(mapping[i]) res.push_back(i);
 }
 cout << res.size() << '\n';
 for(int e:res) cout << e << ' ' << mapping[e] << '\n';
}
```