链接LintCode 炼码 - 更高效的学习体验题解会议室 3使用扫描线算法。这个题用线段树来做其实挺直观的复杂度也能做到 nlognnlogn 但是实在是代码量太大了。所以就看看这个题有没有一些没用到的线段树的功能。进而发现这个题目只需要支持查询不需要支持修改。因此就大概率存在不用线段树的方法。进一步的看这个题并不是每次 ask 都要求你马上返回一个结果而是一口气给你一堆 ask然后一口气 return 一堆结果。因此想到可以用离线算法的思想。因此我们可以把 ask 里面的 Intervals 也和正常开会的 Intervals 混在一起去排序和处理。排序的方法是把 Interval 拆开成为起点和终点位置优先排序位置相同的终点在前起点在后。排序之后从左到右处理也就是扫描线算法了。在扫描的过程中维护一个 ask_set 代表此时扫描线扫到的询问区间有哪些那么如果此时 meetings 的个数 了房间个数 rooms这些 ask_set 里面的区间就都需要标记为 False无法安排会议。一些细节要处理的是由于区间的跨度可能很大有连个地方需要去处理标记情况一个是真实的会议开始的时间点一个是当一个 ask 开始的时间点。1.扫描线start是1end是-1填写端点val2.排序先安装val排序如果val相等则end位-1的排序在前面3.如果当前点是ask判断下当前节点是否是开始累加sumrooms表示当前不能添加该会议了rooms,则将当前的ask添加到ask_set因为后面可能有房间导致不满足调整不是ask对sum n.flag进行累加如果sum rooms表示前面ask_set里面的ask都需要标记为false且清空ask_set后面可能还不满足也可能会重复赋值为falseclass Solution { public: /** * param intervals: the intervals * param rooms: the sum of rooms * param ask: the ask * return: true or false of each meeting */ struct Node { int val; int flag; bool ask; int index; Node(int v, int f, bool a, int i) { val v; flag f; ask a; index i; } }; vectorbool meetingRoomIII(vectorvectorint intervals, int rooms, vectorvectorint ask) { // Write your code here. int len intervals.size(); if (len 0) { return {}; } vectorNode nodes; for (auto v : intervals) { Node node1(v[0], 1, false, -1); Node node2(v[1], -1, false, -1); nodes.push_back(node1); nodes.push_back(node2); } for (int i 0; i ask.size(); i) { vectorint v ask[i]; Node node1(v[0], 1, true, i); Node node2(v[1], -1, true, i); nodes.push_back(node1); nodes.push_back(node2); } sort(nodes.begin(), nodes.end(), [](Node a, Node b) { if (a.val b.val) { return true; } else if (a.val b.val a.flag b.flag) { return true; } return false; }); unordered_setint ask_set; vectorbool result(ask.size(), true); int sum 0; for (auto n : nodes) { if (n.ask) { if (n.flag 0) { if (sum rooms) { result[n.index] false; } else { ask_set.insert(n.index); } } else { ask_set.erase(n.index); } } else { sum n.flag; if (sum rooms) { for (auto index : ask_set) { result[index] false; } ask_set.clear(); } } } return result; } };ask_set.erase(n.index)确实会删除但它只删除询问结束时的那个询问。问题在于在询问结束之前如果期间发生了多次“满员”这个询问会被反复遍历到。具体场景假设有一个询问A它的区间是[1, 100]。在这段时间内已有会议导致房间多次满员比如在时刻 10、30、50、70、90 各满员一次。扫描过程时刻事件ask_set 内容动作1A 开始{A}加入 A10满员{A}遍历{A}标记 A 为 false ❌30满员{A}再次遍历{A}重复标记 ❌50满员{A}再次遍历{A}❌70满员{A}再次遍历{A}❌90满员{A}再次遍历{A}❌100A 结束{}删除 A虽然 A 在第 10 时刻就已经被标记为false但它直到第 100 时刻才被erase。中间的每一次满员都会重新遍历一遍 A。如果有 M 个这样的询问每个都跨越多轮满员时间复杂度就是 O(K × M)K 是满员次数M 是询问数这就超时了。加上clear()后时刻事件ask_set 内容动作1A 开始{A}加入 A10满员{A}遍历{A}标记 falseclear()✅30满员{}空不遍历50满员{}空不遍历......{}不再重复遍历 ✅100A 结束{}erase 无影响每个询问最多被遍历一次总复杂度降到 O(N M)。核心区别操作erase单独eraseclear何时移除询问询问结束时询问第一次遇到满员时或正常结束同一询问被遍历次数多次每次满员都遍历最多 1 次最坏复杂度O(K × M)O(N M)一句话总结erase只在询问自然结束时才移除它无法阻止它在存活期间被反复遍历。clear()则在第一次满员时就把所有等待中的询问一次性清空保证每个询问只被处理一次。两者配合才能避免超时。