// Intervalos semiabiertos [start, finish): una clase que termina a las 10 no se cruza con
// una que empieza a las 10. Siempre start < finish.
#pragma once

#include <algorithm>
#include <cstddef>
#include <functional>
#include <queue>
#include <utility>
#include <vector>

struct Interval {
    int start;
    int finish;
    bool operator==(const Interval&) const = default;
};

inline bool overlap(const Interval& a, const Interval& b) {
    return a.start < b.finish && b.start < a.finish;
}

// Válida: ningún par se cruza. No dice nada sobre si es la más grande posible.
inline bool is_valid(const std::vector<Interval>& chosen) {
    for (std::size_t i = 0; i < chosen.size(); i++) {
        for (std::size_t j = i + 1; j < chosen.size(); j++) {
            if (overlap(chosen[i], chosen[j])) return false;
        }
    }
    return true;
}

// La regla correcta: en orden de finalización, tomar lo que no se cruce con lo último tomado.
inline std::vector<Interval> select_by_finish(std::vector<Interval> classes) {
    std::sort(classes.begin(), classes.end(),
              [](const Interval& a, const Interval& b) { return a.finish < b.finish; });
    std::vector<Interval> chosen;
    for (const Interval& c : classes) {
        // Invariante: chosen es válida y está ordenada por tiempo.
        if (chosen.empty() || chosen.back().finish <= c.start) {
            chosen.push_back(c);
        }
    }
    return chosen;
}

// Un greedy genérico: recorre según una clave y toma lo que no se cruce con nada de lo tomado.
template <typename Key>
std::vector<Interval> greedy_by_key(std::vector<Interval> classes, Key key) {
    std::stable_sort(classes.begin(), classes.end(),
                     [&](const Interval& a, const Interval& b) { return key(a) < key(b); });
    std::vector<Interval> chosen;
    for (const Interval& c : classes) {
        const bool fits = std::none_of(chosen.begin(), chosen.end(),
                                       [&](const Interval& x) { return overlap(x, c); });
        if (fits) chosen.push_back(c);
    }
    return chosen;
}

inline std::vector<Interval> rule_earliest_start(const std::vector<Interval>& classes) {
    return greedy_by_key(classes, [](const Interval& c) { return c.start; });
}

inline std::vector<Interval> rule_shortest(const std::vector<Interval>& classes) {
    return greedy_by_key(classes, [](const Interval& c) { return c.finish - c.start; });
}

inline std::vector<Interval> rule_earliest_finish(const std::vector<Interval>& classes) {
    return greedy_by_key(classes, [](const Interval& c) { return c.finish; });
}

// Cuántas clases de `pool` se cruzan con pool[i], sin contarla a ella.
inline int conflicts(const std::vector<Interval>& pool, std::size_t i) {
    int total = 0;
    for (std::size_t j = 0; j < pool.size(); j++) {
        if (j != i && overlap(pool[i], pool[j])) total++;
    }
    return total;
}

// Menos cruces: entre las clases que quedan, tomar la que menos se cruza con las demás que
// quedan, sacar las que se cruzan con ella y repetir. Con empate, la primera de la lista.
inline std::vector<Interval> rule_fewest_conflicts(std::vector<Interval> pool) {
    std::vector<Interval> chosen;
    while (!pool.empty()) {
        std::size_t best = 0;
        for (std::size_t i = 1; i < pool.size(); i++) {
            if (conflicts(pool, i) < conflicts(pool, best)) best = i;
        }
        const Interval picked = pool[best];
        chosen.push_back(picked);
        std::erase_if(pool, [&](const Interval& c) { return overlap(c, picked); });
    }
    return chosen;
}

// Los tamaños que puede dar menos cruces según cómo se resuelvan los empates: (menor, mayor).
inline std::pair<int, int> fewest_conflicts_range(const std::vector<Interval>& pool) {
    if (pool.empty()) return {0, 0};
    int fewest = conflicts(pool, 0);
    for (std::size_t i = 1; i < pool.size(); i++) {
        fewest = std::min(fewest, conflicts(pool, i));
    }
    int low = static_cast<int>(pool.size());
    int high = 0;
    for (std::size_t i = 0; i < pool.size(); i++) {
        if (conflicts(pool, i) != fewest) continue;
        std::vector<Interval> rest;
        for (const Interval& c : pool) {
            if (!overlap(c, pool[i])) rest.push_back(c);
        }
        const auto [rest_low, rest_high] = fewest_conflicts_range(rest);
        low = std::min(low, rest_low + 1);
        high = std::max(high, rest_high + 1);
    }
    return {low, high};
}

// El óptimo por fuerza bruta: prueba los 2^n subconjuntos. Solo para n pequeño.
inline int max_compatible_brute(const std::vector<Interval>& classes) {
    const unsigned n = static_cast<unsigned>(classes.size());
    int best = 0;
    for (unsigned mask = 0; mask < (1u << n); mask++) {
        std::vector<Interval> subset;
        for (unsigned i = 0; i < n; i++) {
            if (mask & (1u << i)) subset.push_back(classes[i]);
        }
        if (static_cast<int>(subset.size()) > best && is_valid(subset)) {
            best = static_cast<int>(subset.size());
        }
    }
    return best;
}

// ¿Alguna solución óptima contiene a classes[index]? También por fuerza bruta.
inline bool in_some_optimum(const std::vector<Interval>& classes, std::size_t index) {
    std::vector<Interval> rest;
    for (std::size_t i = 0; i < classes.size(); i++) {
        if (!overlap(classes[i], classes[index])) rest.push_back(classes[i]);
    }
    return 1 + max_compatible_brute(rest) == max_compatible_brute(classes);
}

// Cuántas clases hay a la vez en el momento más lleno. En un mismo instante, primero salen
// las que terminan y luego entran las que empiezan: por eso el fin se ordena con -1.
inline int max_simultaneous(const std::vector<Interval>& classes) {
    std::vector<std::pair<int, int>> events;
    for (const Interval& c : classes) {
        events.push_back({c.start, +1});
        events.push_back({c.finish, -1});
    }
    std::sort(events.begin(), events.end());
    int now = 0;
    int most = 0;
    for (const auto& event : events) {
        now += event.second;
        most = std::max(most, now);
    }
    return most;
}

// Reparte las clases en aulas: devuelve el número de aula (desde 0) de cada clase, en el
// orden de entrada. Por orden de inicio, cada clase va a un aula libre si existe.
inline std::vector<int> assign_rooms(const std::vector<Interval>& classes) {
    std::vector<std::size_t> order(classes.size());
    for (std::size_t i = 0; i < order.size(); i++) order[i] = i;
    std::sort(order.begin(), order.end(), [&](std::size_t x, std::size_t y) {
        if (classes[x].start != classes[y].start) return classes[x].start < classes[y].start;
        return x < y;  // con empate, el orden de entrada: así el resultado no depende de std::sort
    });

    using RoomEnd = std::pair<int, int>;  // (hora en que se desocupa, aula)
    std::priority_queue<RoomEnd, std::vector<RoomEnd>, std::greater<RoomEnd>> busy;
    std::vector<int> room(classes.size());
    int opened = 0;
    for (std::size_t i : order) {
        if (!busy.empty() && busy.top().first <= classes[i].start) {
            room[i] = busy.top().second;
            busy.pop();
        } else {
            room[i] = opened++;
        }
        busy.push({classes[i].finish, room[i]});
    }
    return room;
}

inline int rooms_used(const std::vector<int>& room) {
    return room.empty() ? 0 : 1 + *std::max_element(room.begin(), room.end());
}

// Una idea que suena bien para las aulas: llenar la primera con la selección óptima, quitar
// esas clases, llenar la segunda con lo que quede, y así. Devuelve cuántas aulas usa.
inline int rooms_by_repeated_selection(std::vector<Interval> classes) {
    int rooms = 0;
    while (!classes.empty()) {
        std::vector<Interval> filled = select_by_finish(classes);
        for (const Interval& c : filled) {
            classes.erase(std::find(classes.begin(), classes.end(), c));
        }
        rooms++;
    }
    return rooms;
}

// El mínimo de aulas por vuelta atrás, sin usar ningún teorema: se prueba poner cada clase
// en cada aula abierta o en una nueva. Solo para n pequeño.
inline void min_rooms_search(const std::vector<Interval>& classes, std::size_t next,
                             std::vector<std::vector<Interval>>& rooms, int& best) {
    if (static_cast<int>(rooms.size()) >= best) return;
    if (next == classes.size()) {
        best = static_cast<int>(rooms.size());
        return;
    }
    const Interval c = classes[next];
    for (std::size_t r = 0; r < rooms.size(); r++) {
        const bool fits = std::none_of(rooms[r].begin(), rooms[r].end(),
                                       [&](const Interval& x) { return overlap(x, c); });
        if (fits) {
            rooms[r].push_back(c);
            min_rooms_search(classes, next + 1, rooms, best);
            rooms[r].pop_back();
        }
    }
    rooms.push_back({c});
    min_rooms_search(classes, next + 1, rooms, best);
    rooms.pop_back();
}

inline int min_rooms_brute(const std::vector<Interval>& classes) {
    if (classes.empty()) return 0;
    int best = static_cast<int>(classes.size()) + 1;
    std::vector<std::vector<Interval>> rooms;
    min_rooms_search(classes, 0, rooms, best);
    return best;
}