A ideia desse problema é realizar as tarefas de forma a minimizar o tempo que passa após o tempo limite dele acabar.
Podemos achar uma solução gulosa para esse problema. Vamos ordenar as tarefas pelos seus pontos de inicio de forma crescente, e caso haja empate, pelo termino de forma crescente. A partir daí podemos simular pelo tempo e obter a resposta.
A razão por quê isso funciona é pelo fato de se tivermos duas tarefas a e b que teminam uma após a outra, caso colquemos na ordem contraria, teríamos uma solução pior.
Código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| #define D first | |
| #define T second | |
| using namespace std; | |
| typedef pair<int, int> pii; | |
| const int maxn = 10010; | |
| pii v[maxn]; | |
| int main() | |
| { | |
| int n; | |
| cin >> n; | |
| for (int i = 0; i < n; i++) { | |
| cin >> v[i].T >> v[i].D; | |
| } | |
| sort(v, v + n); | |
| long long s = 0; | |
| long long matraso = 0; | |
| for (int i = 0; i < n; i++) { | |
| s += v[i].T; | |
| if (s > v[i].D) matraso = max(matraso, s - v[i].D); | |
| } | |
| cout << matraso << "\n"; | |
| return 0; | |
| } |