yokobuttonの不定期で競技プログラミングをするブログ

不定期で解けた競技プログラミングコンテストの問題を載せています。

東京海上日動プログラミングコンテスト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;
}