[解析アルゴリズムプール]管理BOJ 6068時間

今日の質問は管理BOJ 6068時間です!アルゴリズムの分類を問わず、毎日4つの問題を抽出する今日の質問で解答を行い、黄金5段階の問題です!

管理BOJ 6068時間

誠実な農夫ジョンは時間を効率的に管理することに気づいた.彼はN件のやるべきことに数をつけた(1<=N<=1000).(牛乳搾り、厩舎掃除、壁修理など)
ジョンの時間を効果的に管理するために、彼は完成しなければならない仕事のリストを並べた.完了に要する時間をT i(1<=T i<=1000)と呼び、完了時をS i(1<=S i<=10000)と呼ぶ.農夫のジョンは一日の始まりをt=0と決めた.そして仕事をしている間に、そのことが完成するまで、そのことしかしません.
ジョンは朝寝坊が好きだ.そのため、時間通りに終わることが決められる場合は、ジョンが一番遅く起きてもいい時間をプリントアウトします.

にゅうしゅつりょく

私の答え

すべてのことに時間帯があるので、時間帯は一番遅いことから埋めるべきだと思います.グリディアルゴリズムのようなものです<algorithm>ヘッダのsort関数を用いて、所定の事柄を含む配列taskをdedrineの遅い順に並べ替え、int型変数limitの値をtask[0].secondに初期化し、制限値を低減する.
limitがタスクのdedrainより大きい場合は、limitをdedrainにドラッグすると、タスクを実行するのに要する時間に応じてlimitが減少します.
すべてのタスクを探索した後、limitは怠け者のジョンがlimit時間に発生すれば、すべてのことは時間内に完成することができ、limit値が0未満であれば、与えられた時間内にすべてのタスクを完成することができないので、-1を出力します.

コード#コード#

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 데드라인 순으로 내림차순 정렬 
bool byDeadLine(pair<int, int> a, pair<int, int> b){
    if (a.second == b.second){
        return a.first>b.first;
    }else{
        return a.second > b.second;
    }
}

int getLatestTime(int N, vector<pair<int, int>> task){
    sort(task.begin(), task.end(), byDeadLine);

    int limit = task[0].second;
    for (int i = 0; i < N; ++i) {
        if (limit > task[i].second){  // limit을 데드라인으로 땡겨옴 
            limit = task[i].second;
        }
        limit -= task[i].first;  // 업무 수행 시간 만큼 줄임 
    }

    return limit;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin>>N;

    int need=-1, deadline=-1;
    vector<pair<int, int>> task;
    for (int i = 0; i < N; ++i) {
        cin>>need>>deadline;
        task.push_back(make_pair(need, deadline));
    }

    int wakeup = getLatestTime(N, task);
    if (wakeup < 0) wakeup = -1;

    cout<<wakeup;

    return 0;
}