Job Scheduling

이 유형은 문제에서 주어진 조건에 따라 풀이 방법이 매우 다양하게 나뉠 수 있다.

작업 배정을 할지 안할지만 결정

• 회의실 배정 문제: https://www.acmicpc.net/problem/1931
• 가젤 님의 관련 티스토리 글 (+ 아래 사진 출처): https://gazelle-and-cs.tistory.com/59

// Greedy 기초
// 작업을 진행하는데 걸리는 시간 T가 주어지지 않았다.
// 그 작업을 채택할지 안할지만 보면 된다.

// 1. 정렬 Phase
// 끝나는 시간 기준으로 정렬한다.
// 2. 할당 Phase
// 앞에서부터 차례대로 할당한다.
struct Meeting {
    int s, e;
};

void solve(vector<Meeting>& v) {
    sort(v.begin(), v.end(), [&](Meeting& a, Meeting& b) -> bool {
        if (a.e != b.e) return a.e < b.e;
        return a.s < b.s;
    });
    
    int last = 0;
    int ans = 0;
    for(auto& item: v) {
        if (item.s >= last) ++ans, last = item.e;
    }
    printf("%d\n", ans);
}

작업 끝시간(Deadline)과 수행하는 데 걸리는 시간(T)가 주어진 경우

• Backward Scheduling 하면 풀리는 유형
• 시간 관리 문제: https://www.acmicpc.net/problem/1263

struct Job {
    int t;
    int d; // deadline
    bool operator<(const Job& t) const {
        if (d != t.d) return d > t.d;
        return this->t < t.t;
    }
};

void solve(vector<Job>& v) {
    sort(v.begin(), v.end());

    int ctime = v[0].d - v[0].t;
    for(int i = 1; i < v.size(); ++i) {
        ctime = min(ctime, v[i].d); // backward scheduling
        ctime -= v[i].t;
    }
    if (ctime < 0) printf("-1\n");
    else printf("%d\n", ctime);
}

작업 수행 시간이 T = 1인 경우

• ABC 325 Round D번: https://atcoder.jp/contests/abc325/tasks/abc325_d

// 기본적으로 시간을 1부터 끝까지 훑으면서 할당하는 것
// 다만, 더 이상 후보군이 없을 때는 기록이 있는 지점부터 다시 시작
// -> 이렇게 안하면 구간 클 경우 TLE

// 과정을 다시 요약하면 아래와 같다. (time에 대한 sliding window 기법)
// 1. 가장 r_i가 작은 시간 작업부터 시작
// 1-1. r_i와 같은 시간에 시작하는 작업들은 모두 pq에 넣는다.
// 2. 그 중 d_i가 가장 짧은 녀석부터 시간을 1씩 증가시켜가면서 실제로 할당한다.
// 2-1. 할당할 때 한번에 다 하는게 아니라, 현재 시간에 1개만 할당하고, 다음 시간을 연속해서 보면서 할당한다.
// 3. 만약 보려는 녀석이 이미 보고있는 시간대를 지나갔다면 버린다.
void solve(map<ll, priority_queue<ll, vector<ll>, greater<>>>& M) {
    // M[a] = {1, 2, 3} - a 시간에 시작하는 일이 1, 2, 3에 끝나는 3가지가 있다.
    int ans = 0;
    // unit time: 1임
    ll ctime = 0;
    priority_queue<ll, vector<ll>, greater<>> gpq; // global pq

    auto it = M.begin();
    for(ll ctime = 1; ; ++ctime) { // 시간을 증가시켜가면서 본다.
        if (gpq.size() == 0) {
            // 아무것도 없으니 내맘대로 시간을 맞춘다~
            if (it == M.end()) break;
            auto& cur = *it;
            ctime = cur.first;
            ++it;
        }
        if (M.find(ctime) != M.end()) {
            it = M.find(ctime);
            auto& cur = *it;
            auto& pq = cur.second;
            while(pq.size()) gpq.push(pq.top()), pq.pop();
            ++it;
        }
        // 유효하지 않은 gpq 값을 꺼낸다.
        while (gpq.size() && gpq.top() < ctime) gpq.pop();
        // pq에서 가장 작은거 하나 꺼내서 쓴다.
        if (gpq.size()) {
            gpq.pop();
            ++ans;
        }
    }
    printf("%d\n", ans);
}

Release Time, Deadline 이 존재하며, 주어진 특정 시간에만 작업을 수행하는 유형

• 소가 길을 건너간 이유 4 문제: https://www.acmicpc.net/problem/14464
• 위 유형의 열화판.
  • Release Time이 빠른 녀석부터 보면서 Deadline을 PQ에 저장하는 것까지는 똑같은데, 특정 시간에만 작업잉 수행이 가능하다는 것은 특정 시간만 보면 된다는 의미이고, 특정 시간을 순회하면서 체크하면 된다.

void solve(vector<int>& chicken, vector<pair<int,int>>& cow, int N, int M) {
    sort(cow.begin(), cow.end());
    sort(chicken.begin(), chicken.end());

    // deadline을 순서대로 넣자. 현재 유효한 녀석들만 들어가 있게 된다.
    priority_queue<int, vector<int>, greater<>> pq;
    int cowPtr = 0;
    int ans = 0;
    
    for(auto& c: chicken) {
        int cur = c; // 현재 보는 chicken의 T_i
        for(; cowPtr < M; ++cowPtr) {
            if (cow[cowPtr].y < cur) continue; // 버린다. 이미 다 지나갔다.
            if (cow[cowPtr].x <= cur && cur <= cow[cowPtr].y) {
                pq.push(cow[cowPtr].y); // deadline 순서로 정렬하는 pq에 넣기.
            } else {
                // 앞으로 쓸 녀석들을 만났다. 더이상 pq에 넣지않고 종료
                break;
            }
        }
        while(pq.size() && pq.top() < cur) pq.pop(); // 유효하지 않은것 버리기
        if (pq.size()) {
            // printf("[d] deadline: %d / chicken: %d matched!\n", pq.top(), cur);
            pq.pop();
            ++ans;
        }
    }   
    printf("%d\n", ans);
}

전부 할당해야할 때 필요한 최소 기계의 수를 계산하는 유형

• 강의실 배정 문제: https://www.acmicpc.net/problem/11000

struct Range {
    int l, r;
    bool operator<(const Range& t) {
        if (l != t.l) return l < t.l;
        return r < t.r;
    }
};

void solve(vector<Range>& v) {
    sort(v.begin(), v.end()); // 빨리 시작하는 순서대로 정렬

    priority_queue<int, vector<int>, greater<>> pq;
    for(auto& item: v) {
        if (pq.size() == 0) {
            pq.push(item.r);
            continue;
        }
        if (item.l >= pq.top()) { // 일단 들어갈 수 있다.
            pq.pop();
            pq.push(item.r); // 기존 녀석을 대체
        } else { // 못들어가는 case이다. (현재 가장 빨리 끝나는 녀석보다도 시작이 빠름)
            pq.push(item.r);
        }
    }

    printf("%ld\n", pq.size());
}

Time Complexity

• 우선 순위 큐 베이스 알고리즘이기 때문에 모두 $O(N\log N)$