Unofficial Analysis

Explanation

Notice that the meta is to process shorter tasks before longer tasks.

For some intuition regarding this, think of two tasks that take $5$ and $7$ time units to complete. Notice that no matter what the deadlines are, it's always optimal to complete the shorter task first.

To prove this more concretely, let's take $n$ tasks, with durations $t_1, t_2, \cdots, t_n$ and deadlines $d_1, d_2, \cdots, d_n$. Say we complete them in an order such that $a_i$ is the number of the $i$th task completed, making $a_1, a_2, \cdots, a_n$ a permutation of $1$ through $n$.

The final reward is then

Rearranging the formula, we can get

Try expanding them to see why these two are equal!

From this, we can see that we must minimize smaller values of $i$, which is then equivalent to processing shorter tasks first.

Implementation

Time complexity: $\mathcal{O} (N \log N)$

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

using std::cout;
using std::endl;

int main() {
	int task_num;
	std::cin >> task_num;

Copy
import java.io.*;
import java.util.*;

public class TasksNDeadlines {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int taskNum = Integer.parseInt(read.readLine());
		int[][] tasks = new int[taskNum][];
		for (int t = 0; t < taskNum; t++) {
			StringTokenizer task = new StringTokenizer(read.readLine());

Copy
tasks = []
for _ in range(int(input())):
	duration, deadline = [int(i) for i in input().split()]
	tasks.append((duration, deadline))

tasks.sort()

time = 0
reward = 0
for duration, deadline in tasks:
	time += duration
	reward += deadline - time

print(reward)