CSES 2. Tasks and Deadlines (1630)

출처: https://cses.fi/problemset/task/1630

---

문제 설명

You have to process n tasks. Each task has a duration and a deadline, and you will process the tasks in some order one after another. Your reward for a task is d−f where d is its deadline and f is your finishing time. (The starting time is 0, and you have to process all tasks even if a task would yield negative reward.)

What is your maximum reward if you act optimally?

입력 

The first input line has an integer n: the number of tasks.

After this, there are n lines that describe the tasks. Each line has two integers a and d: the duration and deadline of the task.

출력

Print one integer: the maximum reward.

입력 예

3
6 10
8 15
5 12

출력 예

2

제약조건

• 1 <= n  <= 2x10^5
• 1 <= a,d  <= 10^6

---

문제 풀이 

입력받은 업무를 필요 시간을 기준으로 정렬한다.

일은 같이 진행할 수 없기 때문에 전체 업무를 끝내는 시간은 필요 시간 전체의 합으로 고정되어 있으므로, 보상이 큰 일을 먼저 하도록 한다. 필요시간이 짧은 순서로 보상을 계산하기 위해서, 처음부터 진행한 시간과 보상을 기록해서 출력한다.

프로그램 내용

...
    vector <pair <int, int> > t_list;

    for (int idx = 0; idx < nTask; idx++)
        t_list.push_back({t_start, t_end});

    sort(t_list.begin(), t_list.end());

    long reward = 0, t_now=0;

    for (int idx = 0; idx < nTask; idx++)
        reward += t_list[idx].second - (t_list[idx].first + t_now);
        t_now += t_list[idx].first;
...

 

Sorting and Searching ( link )