// tasks/interval/source.cpp
// Interval operations: merge overlapping intervals + greedy activity selection.
// Agents must migrate this to Rust (no HashMap, no unsafe).
//
// Key invariants:
//   - mergeIntervals: sort by start, merge overlapping OR touching ([1,3],[3,5] → [1,5])
//   - maxSchedule: greedy activity selection — sort by end time, pick non-overlapping
//     (touching allowed: [1,3] and [3,5] are compatible)
//   - Both functions return sorted, deterministic results

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using Interval = std::pair<int64_t, int64_t>;

// Merge all overlapping or touching intervals.
// Input does not need to be sorted.
std::vector<Interval> merge_intervals(std::vector<Interval> ivs) {
    if (ivs.empty()) return {};
    std::sort(ivs.begin(), ivs.end());   // sort by start (then end)
    std::vector<Interval> result;
    result.push_back(ivs[0]);
    for (size_t i = 1; i < ivs.size(); i++) {
        auto& [ls, le] = result.back();
        auto [s, e] = ivs[i];
        if (s <= le) {
            // overlapping or touching — extend
            le = std::max(le, e);
        } else {
            result.push_back({s, e});
        }
    }
    return result;
}

// Greedy activity selection: maximize the number of non-overlapping intervals.
// Two intervals are compatible if one ends before (or exactly when) the other starts.
std::vector<Interval> max_schedule(std::vector<Interval> ivs) {
    if (ivs.empty()) return {};
    // Sort by end time (ascending), ties broken by start time
    std::sort(ivs.begin(), ivs.end(), [](const Interval& a, const Interval& b) {
        return a.second < b.second || (a.second == b.second && a.first < b.first);
    });
    std::vector<Interval> result;
    int64_t last_end = std::numeric_limits<int64_t>::min();
    for (auto& [s, e] : ivs) {
        if (s >= last_end) {    // compatible: start >= last selected end
            result.push_back({s, e});
            last_end = e;
        }
    }
    return result;
}

int main() {
    std::vector<Interval> ivs = {{1,3},{2,5},{7,9}};
    auto merged = merge_intervals(ivs);
    std::cout << "merge([1,3],[2,5],[7,9]):\n";
    for (auto& [s, e] : merged)
        std::cout << "  [" << s << "," << e << "]\n";  // [1,5],[7,9]

    std::vector<Interval> activities = {{1,3},{2,4},{3,5}};
    auto scheduled = max_schedule(activities);
    std::cout << "max_schedule([1,3],[2,4],[3,5]):\n";
    for (auto& [s, e] : scheduled)
        std::cout << "  [" << s << "," << e << "]\n";  // [1,3],[3,5]
    return 0;
}