Busca Exaustiva
A implementação da Busca Exaustiva nesse problema foi quebrada em 3 partes, sendo elas a criação de todas as possibilidades, a validação das possibilidades e a busca exaustiva em si. A função create_all_valid_possibilities passa por cada um das permutações de filmes existentes e só adiciona essa possibilidade na lista de possibilidades válidas ao passar pela função de validate_possibility, que irá fazer todas as checagens necessárias para ver se de fato a possibilidade é válida ou não. Tendo todas as possibilidades válidas, a função exhaustive_search irá realizar a busca exaustiva de fato, retornando aquela possibilidade que tem o maior número de filmes alocados.
Implementação
#include <map>#include <vector>#include <iostream>#include <algorithm>#include <chrono>using namespace std;struct movie { int start; int end; int category;};bool order(movie a, movie b) { if (a.start < b.start) { return true; } else if (a.start == b.start) { return a.end < b.end; } else { return false; }}bool validate_possibility(vector<movie> possibility, map<int, int> category_limit) { int n = possibility.size(); vector<int> available_times; for (int i = 0; i < 24; i++) { available_times.push_back(i); } for (int i = 0; i < n; i++) { if (possibility[i].start < possibility[i].end) { for (int j = possibility[i].start; j < possibility[i].end; j++) { if (find(available_times.begin(), available_times.end(), j) == available_times.end()) { return false; } } if (category_limit[possibility[i].category] > 0) { category_limit[possibility[i].category] -= 1; for (int k = possibility[i].start; k < possibility[i].end; k++) { available_times.erase(remove(available_times.begin(), available_times.end(), k), available_times.end()); } } else { return false; } } else { return false; } } return true;}vector<vector<movie>> create_all_valid_possibilities(vector<movie> movies, map<int, int> category_limit) { vector<vector<movie>> all_valid_possibilities; for (int i = 0; i < (1 << movies.size()); i++) { vector<movie> possibility; for (int j = 0; j < movies.size(); j++) { if (i & (1 << j)) { possibility.push_back(movies[j]); } } if (validate_possibility(possibility, category_limit)) { all_valid_possibilities.push_back(possibility); } } return all_valid_possibilities;}vector<movie> exhaustive_search(vector<vector<movie>> all_valid_possibilities) { int n = all_valid_possibilities.size(); int best_possibility_size = 0; vector<movie> best_possibility; for (vector<movie> valid_possibility : all_valid_possibilities) { if (valid_possibility.size() > best_possibility_size) { best_possibility_size = valid_possibility.size(); best_possibility = valid_possibility; } } return best_possibility;}int main() { int n, c; cin >> n >> c; vector<movie> movies; map<int, int> category_limit; for (int i = 0; i < c; i++) { int limit; cin >> limit; category_limit[i+1] = limit; } for (int i = 0; i < n; i++) { int start, end, category; cin >> start >> end >> category; movies.push_back({start, end, category}); } auto start = std::chrono::high_resolution_clock::now(); vector<vector<movie>> all_valid_possibilities = create_all_valid_possibilities(movies, category_limit); vector<movie> best_possibility = exhaustive_search(all_valid_possibilities); auto finish = std::chrono::high_resolution_clock::now(); std::chrono::duration<double> elapsed = finish - start; cout << 1 << ' ' << n << ' ' << c << ' ' << best_possibility.size() << ' ' << elapsed.count() << endl; return 0;}