贪心算法区间调度问题c++算法演示

以下是一个使用C++实现贪心算法解决区间调度问题的示例代码：

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

// 区间结构体
struct Interval {
    int start;
    int end;
};

// 比较函数，根据结束时间排序
bool compareIntervals(Interval a, Interval b) {
    return a.end < b.end;
}

// 贪心算法解决区间调度问题
int intervalScheduling(std::vector<Interval>& intervals) {
    // 按照结束时间排序
    std::sort(intervals.begin(), intervals.end(), compareIntervals);
    
    int count = 1;  // 最少需要一个区间
    int endTime = intervals[0].end;
    
    // 遍历区间，选择结束时间最早的不冲突区间
    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i].start >= endTime) {
            count++;
            endTime = intervals[i].end;
        }
    }
    
    return count;
}

int main() {
    std::vector<Interval> intervals = {{1, 3}, {2, 4}, {3, 6}, {5, 7}, {6, 8}};
    int result = intervalScheduling(intervals);
    
    std::cout << "最多可安排的任务数量: " << result << std::endl;
    
    return 0;
}

在这个示例中，我们定义了一个`Interval`结构体来表示区间，并实现了一个比较函数`compareIntervals`，用于根据结束时间对区间进行排序。`intervalScheduling`函数使用贪心算法解决区间调度问题，首先对区间按照结束时间进行排序，然后从第一个区间开始遍历，选择结束时间最早的不冲突区间，并计数。最后输出最多可安排的任务数量。

在主函数中，我们创建了一个包含几个区间的示例输入，然后调用`intervalScheduling`函数计算结果，并输出最多可安排的任务数量。

注意：这只是一个简单的示例，实际问题可能需要根据具体情况进行更复杂的处理。