区間スケジューリング問題 キーエンス プログラミング コンテスト 2020 B -Robot Arms

けんちょん本P112-　貪欲法　区間スケジューリング問題

問題

B - Robot Arms

座標Xiに左右にLiだけの操作範囲を持つロボットが設置されているとき，操作範囲が重ならないように何個のロボットを残せるかという問題です。

入力にひと手間あるものの，典型的な区間スケジューリング問題です。

考察

アームの左端と右端をPair配列にし，右端でソートして左側から重ならないようにおけるロボットをカウントしていきます。

メモ

・　pairのソートはfirstの昇順，firstが同じ要素についてはsecondの昇順
・　push_backは要素数を増やしながら追加できる

提出コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
  int N;
  cin>>N;
  vector<pair<ll,ll>>P;
  for(int i=0;i<N;i++){
    int x,l;
    cin>>x>>l;
    P.push_back({x+l,x-l});
  }
  sort(P.begin(),P.end());
  int cnt=0;
  ll temp=-10e9;
  for(int i=0;i<N;i++){
    //cout<<temp<<" "<<P[i].first<<" "<<P[i].second<<endl;
    if(P[i].second>=temp){
      cnt++;
      temp=P[i].first;
    }
  }
  cout<<cnt<<endl;
  return 0;   
}