编辑代码

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

struct Interval {
    int start;
    int end;

    Interval(int s, int e) : start(s), end(e) {}
};

bool compareIntervals(const Interval& a, const Interval& b) {
    return a.end < b.end;
}

std::vector<Interval> maximumNonOverlappingIntervals(const std::vector<Interval>& intervals) {
    std::vector<Interval> result;
    
    // 对区间按结束端点进行排序
    std::vector<Interval> sortedIntervals = intervals;
    std::sort(sortedIntervals.begin(), sortedIntervals.end(), compareIntervals);

    // 贪心选择不相交的区间
    int currentEnd = -1;
    for (const Interval& interval : sortedIntervals) {
        if (interval.start > currentEnd) {
            result.push_back(interval);
            currentEnd = interval.end;
        }
    }

    return result;
}

int main() {
    std::vector<Interval> intervals = {
        Interval(6, 8),
        Interval(2, 4),
        Interval(3, 5),
        Interval(1, 5),
        Interval(5, 9),
        Interval(8, 10)
    };

    std::vector<Interval> result = maximumNonOverlappingIntervals(intervals);

    std::cout << "Maximum non-overlapping intervals: ";
    for (const Interval& interval : result) {
        std::cout << "[" << interval.start << ", " << interval.end << "] ";
    }
    std::cout << std::endl;

    return 0;
}