東京海上日動プログラミングコンテスト2022(AtCoder Beginner Contest 256)D - Union of Interval
問題の要約
実数L,Rに対して、L以上R未満からなる次数の集合を[L,R)と表す。このような形で表される集合を右半開区間という。
N個の右半開区間[Li,Ri)が与えられる。これらの和集合をSとする。Sを最小の個数の右半開区間の和集合として表せ。
制約
1<=N<=2*10^5
1<=Li<Ri<=2*10^5
入力
N
L1 R1
...
LN RN
出力
Sが最小でk個の右半開区間の和集合で表せるとする。そのようなk個の右半開区間[Xi,Yi)をXiの昇順で以下のようにk行出力せよ。
X1 Y1
...
Xk Yk
考え方
1,[Li,Ri)をvector<pair<int,int>> LRで管理する。
2,[Li,Ri)と[Lj,Rj)(i<j)を考えると、大小関係を考えるのが面倒くさいので、ソートをして、[Li,Ri)<=[Lj,Rj)(i<j)を確定してしまう。
3,考えるべき大小関係は大きく分けて
Ri < Lj : 加えて、もしRi<Rjならば[Li,Rj)としてよい。
Lj <= Ri : [Lj,Rj)は新しく起点となる右半開区間である。
の2つとなる。
4,ソートしているので、LRの最初から順に大小関係を考えていけばよい。
実際のプログラム
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int main(){
int N;
cin >> N;
vector<pair<int,int>> LR(N);
for(int i = 0; i < N; ++i){
cin >> LR[i].first >> LR[i].second;
}
sort(LR.begin(), LR.end());
vector<pair<int,int>> ans;
for(auto it = LR.begin(); it != LR.end();){
if(ans.empty()){
ans.push_back(*it);
++it;
}else if( (*it).first <= ans[ans.size()-1].second){
if(ans[ans.size()-1].second < (*it).second){
ans[ans.size()-1].second = (*it).second;
}
++it;
}else{
ans.push_back(*it);
++it;
}
}
for(int i = 0; i < static_cast<int>(ans.size()); ++i){
cout << ans[i].first <<" "<< ans[i].second << endl;
}
return 0;
}