Skip to Content
CTRL K

Tasks & Deadlines

Análisis no oficial 

Explicación

Nótese que la meta es procesar las tareas más cortas antes que las más largas.

Para cierta intuición al respecto, pensemos en dos tareas que tardan 55 y 77 unidades de tiempo. Nótese que, sean cuales sean los plazos, siempre es óptimo completar primero la tarea más corta.

Para demostrarlo de forma más concreta, tomemos nn tareas, con duraciones t1,t2,⋯ ,tnt_1, t_2, \cdots, t_n y plazos d1,d2,⋯ ,dnd_1, d_2, \cdots, d_n. Digamos que las completamos en un orden tal que aia_i es el número de la ii-ésima tarea completada, de modo que a1,a2,⋯ ,ana_1, a_2, \cdots, a_n es una permutación de 11 a nn.

La recompensa final es entonces

(da1−ta1)+(da2−(ta1+ta2))+⋯+(dan−∑i=1ntai) (d_{a_1}-t_{a_1})+(d_{a_2}-(t_{a_1}+t_{a_2}))+\cdots+\left(d_{a_n}-\sum_{i=1}^n t_{a_i}\right)

Reordenando la fórmula, obtenemos

∑i=1ndai−∑i=1ntai(n+1−i) \sum_{i=1}^n d_{a_i} - \sum_{i=1}^n t_{a_i}(n+1-i)

¡Intenta expandirlas para ver por qué estas dos son iguales!

De esto se ve que debemos minimizar los valores más pequeños de ii, lo que equivale a procesar primero las tareas más cortas.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O} (N \log N)

#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
 
int main() {
	int task_num;
	std::cin >> task_num;
	std::vector<std::pair<int, int>> tasks(task_num);
	for (auto &[duration, deadline] : tasks) { std::cin >> duration >> deadline; }
 
	std::sort(tasks.begin(), tasks.end());
 
	long long time = 0;
	long long reward = 0;
	for (const auto &[duration, deadline] : tasks) {
		time += duration;
		reward += deadline - time;
	}
 
	cout << reward << endl;
}
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());
			tasks[t] = new int[] {
			    Integer.parseInt(task.nextToken()),  // duration
			    Integer.parseInt(task.nextToken())   // deadline
			};
		}
 
		Arrays.sort(tasks, Comparator.comparingInt(t -> t[0]));
 
		long time = 0;
		long reward = 0;
		for (int[] t : tasks) {
			time += t[0];
			reward += t[1] - time;
		}
 
		System.out.println(reward);
	}
}
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)
Fundamentos