백준 11666 : 워크스테이션 배정 (그리디)

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

11666번: 워크스테이션 배정

풀이
1. 끝난지 m분이 초과하지 않은 스테이션 중 가장 먼저 끝난 스테이션에 배정하는것이 최적
2. 그런것이 없다면 새로운 스테이션에 배정하는것이나 다시 잠긴 스테이션에 배정하는 것이나 동일함
3. 연구원이 들어오는 시간을 기준으로 정렬했을 때 한 연구원을 기준으로 잠기는 스테이션은 다음으로 들어오는 연구원 기준으로도 모두 잠기게 되어있음

multiset 사용
처음엔 set을 사용했으나 중복값이 존재하기 때문에 multiset을 사용해야함.
multiset에서 erase의 매개변수를 값으로 준다면 해당 값과 동일한 모든 키를 삭제한다.
iterator를 매개변수로 준다면 해당 iterator만 삭제한다.
삭제 및 삽입에 걸리는 시간은 logn
=> nlogn

우선순위큐 사용
풀이의 3번 기준에 의해 사용되지 않는 값들을 pop한다 해도 다시 사용할 일이 없음 => 효율적
pq의 삽입 및 삭제는 logn, 코드는 우선순위 큐를 이용한 코드
=> nlogn

 

 

#include<bits/stdc++.h>
#include<time.h>


#define MAX 1000000007
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, -1, 0, 1, 1, 1, -1, -1 };
int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }


int main() {
    init();
    ll ans = 0;
    priority_queue<int> work;
    ll n, m; cin >> n >> m;
    vector<pii> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end());

    for (int i = 0; i < n; i++) {
        ll a = v[i].first;
        ll s = v[i].second;

        while (!work.empty()) {
            if (-work.top() > a)
                break;

            int t = -work.top();
            work.pop();
            if (t >= a - m && t <= a) {
                ans++;
                break;
            }
        }

        work.push(-(a + s));
    }
    cout << ans << "\n";
    
}