c++贪心算法（会场安排、区间选点）示例

贪心算法介绍

贪心算法是一种常见的算法思想，其在求解最优化问题时，采用每一步都选择当前最优解的策略。贪心算法的核心思想是通过局部最优的选择来达到全局最优。

会场安排问题

会场安排问题是一个经典的贪心算法应用场景。假设有一系列的会议，每个会议包含开始时间和结束时间。我们希望找到一种安排策略，使得会议之间不冲突，并且能安排尽可能多的会议。

为了解决这个问题，我们可以按照结束时间对会议进行排序，然后从第一个会议开始，依次选择结束时间最早的会议。如果选择当前会议不与已选择的会议冲突，则将其加入已选择的会议列表，并更新当前结束时间。如此循环，直到遍历完所有的会议。

#include 
#include 
#include 

struct Meeting {
    int start;
    int end;
};

bool compare(Meeting m1, Meeting m2) {
    return m1.end < m2.end; // 按结束时间升序排序
}

int maxMeetingCount(std::vector& meetings) {
    std::sort(meetings.begin(), meetings.end(), compare); // 按结束时间排序

    int count = 0;
    int currentEnd = 0;

    for (const Meeting& meeting : meetings) {
        if (meeting.start >= currentEnd) {
            count++;
            currentEnd = meeting.end;
        }
    }

    return count;
}

int main() {
    std::vector meetings = {{1, 3}, {2, 4}, {3, 5}, {4, 6}, {5, 7}};
    int maxCount = maxMeetingCount(meetings);
    std::cout << "最多可安排的会议数为：" << maxCount << std::endl;

    return 0;
}

以上代码中，我们通过自定义的compare函数对会议按照结束时间升序排序。然后使用maxMeetingCount函数计算最多可安排的会议数。结果为3，表示在给定的会议列表中，最多可以安排3个会议。

区间选点问题

区间选点问题是另一个贪心算法的经典应用案例。给定一些闭区间，从中选出尽量少的点，使得每个区间都至少包含一个选出来的点。

为了解决这个问题，我们可以按照区间的结束位置进行排序。然后从第一个区间开始，选择该区间的结束位置作为选定的点，之后将与该点相交的区间全部排除。如此循环，直到遍历完所有的区间。

#include 
#include 
#include 

struct Interval {
    int start;
    int end;
};

bool compare(Interval i1, Interval i2) {
    return i1.end < i2.end; // 按结束位置升序排序
}

std::vector selectPoints(std::vector& intervals) {
    std::sort(intervals.begin(), intervals.end(), compare); // 按结束位置排序

    std::vector points;
    int currentEnd = intervals[0].end;

    points.push_back(currentEnd);

    for (const Interval& interval : intervals) {
        if (interval.start > currentEnd) {
            currentEnd = interval.end;
            points.push_back(currentEnd);
        }
    }

    return points;
}

int main() {
    std::vector intervals = {{1, 3}, {2, 4}, {3, 5}, {4, 6}, {5, 7}};
    std::vector selectedPoints = selectPoints(intervals);

    std::cout << "选出的点的位置为：";
    for (const int& point : selectedPoints) {
        std::cout << point << " ";
    }
    std::cout << std::endl;

    return 0;
}

以上代码中，我们通过自定义的compare函数对区间按照结束位置升序排序。然后使用selectPoints函数选择尽可能少的点，将选出的点存放在返回的vector中。输出结果为“选出的点的位置为：3 6”，表示从给定的区间中，可以选择3和6作为满足条件的点。

总结

贪心算法是一种常用的算法思想，在一些特定问题的求解过程中，可以提供高效且近似最优的解。会场安排问题和区间选点问题是贪心算法的经典应用场景，在实际开发中可以借鉴这些思路解决类似的问题。

需要注意的是，贪心算法的应用需要谨慎选择，有些问题并不适合使用贪心算法进行求解，可能会得到不正确的结果。因此，在实际使用中需要进行充分的问题分析和验证。