Spaces:
Sleeping
Sleeping
File size: 2,590 Bytes
bf9c466 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | // 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;
}
|