[알고리즘] 백준 14469 // 그리디, 라인스위핑은 막대기를 그려라

https://www.acmicpc.net/problem/14469

* 풀이1

• pq로 비비려다가 망함

 

* 풀이2

• 시간문제는 수직선으로 표현하라.

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

int n,ret;
vector<pair<int,int>> v; // <도착시, 검문시 >

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   cin>>n;
   for (int i=0;i<n;++i) {
      int a,b;
      cin>>a>>b;
      v.push_back({a,b});
   }
   sort(v.begin(),v.end());

   int time=v[0].first+v[0].second;
   for (int i=1;i<n;++i) {
      time=max(time,v[i].first);
      time+=v[i].second;
   }
   cout<<time;
   return 0;
}