给出lintcode919的c++完整可运行包含主函数的代码

<think>好的，我现在需要帮助用户获取LintCode 919题的完整可运行的C++代码，包括主函数。首先，我需要确定LintCode 919题的具体内容。根据我的知识库，LintCode 919题目是关于会议室II的问题，即给定一系列会议的开始和结束时间，计算需要的最少会议室数量。 接下来，用户需要的是C++的完整代码，包含主函数。这意味着不仅要提供算法核心，还要有输入输出的示例，以便用户可以直接编译和运行测试。 首先，我应该回顾会议室II的标准解法。这个问题通常使用排序和优先队列（最小堆）来解决。步骤如下： 1. 将会议按开始时间排序。 2. 使用最小堆来跟踪当前正在进行的会议的结束时间。 3. 遍历每个会议，如果当前会议的开始时间大于堆顶的结束时间（即最早结束的会议），则复用该会议室，弹出堆顶；否则需要新会议室。然后将当前会议的结束时间加入堆中。 4. 堆的大小即为所需的最少会议室数量。 接下来，我需要将这个逻辑转化为C++代码。注意处理输入输出，例如用户可能需要从标准输入读取数据，或者直接在代码中提供测试用例。为了方便用户测试，主函数里可以包含一个示例输入，比如题目中的样例输入：[[0,30],[5,10],[15,20]]，预期输出是2。 然后考虑代码的结构。使用vector存储会议时间，排序时需要自定义比较函数，按开始时间升序排列。优先队列默认是最大堆，所以需要使用greater<int>来建立最小堆，这样堆顶是最早结束时间。 此外，需要注意代码的可读性和规范性，比如正确的头文件包含（如#include <vector>，#include <algorithm>，#include <queue>等），以及使用using namespace std;来简化代码。 主函数部分，需要构造输入数据，调用函数，并输出结果。例如： vector<vector<int>> intervals = {{0,30},{5,10},{15,20}}; 然后输出minMeetingRooms(intervals)。 在编写代码时，要确保语法正确，比如使用正确的括号，分号等。同时，要处理可能的边界情况，比如没有会议时返回0。 最后，生成相关问题，帮助用户进一步理解该问题，例如询问时间复杂度、不同解法比较、空间复杂度优化等。</think>### LintCode 919 会议室II C++完整代码实现 以下是包含主函数的完整可运行代码，采用排序+优先队列的标准解法： ```cpp #include <vector> #include <algorithm> #include <queue> using namespace std; int minMeetingRooms(vector<vector<int>>& intervals) { if (intervals.empty()) return 0; // 按开始时间排序 sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; }); // 最小堆存储结束时间 priority_queue<int, vector<int>, greater<int>> heap; for (auto& meeting : intervals) { if (!heap.empty() && meeting[0] >= heap.top()) { heap.pop(); } heap.push(meeting[1]); } return heap.size(); } int main() { // 测试样例：[[0,30],[5,10],[15,20]] → 输出2 vector<vector<int>> intervals = {{0,30}, {5,10}, {15,20}}; cout << "Minimum meeting rooms required: " << minMeetingRooms(intervals) << endl; return 0; } ``` ### 代码说明 1. **排序处理**：将会议按开始时间升序排列，时间复杂度$O(n \log n)$ 2. **优先队列**：维护当前正在使用的会议室结束时间，堆顶始终是最早结束的会议室 3. **贪心策略**：每次检查是否可以复用最早释放的会议室（比较当前会议开始时间与堆顶结束时间） 4. **时间复杂度**：$O(n \log n)$，空间复杂度$O(n)$ ### 测试方法 1. 编译执行即可看到示例输出 2. 修改main函数中的intervals数组测试其他用例 3. 例如测试[[7,10],[2,4]]应输出1