class Solution {
public:
int maxEvents(vector<vector<int>>& events) {
}
};
1353. 最多可以参加的会议数目
给你一个数组 events
,其中 events[i] = [startDayi, endDayi]
,表示会议 i
开始于 startDayi
,结束于 endDayi
。
你可以在满足 startDayi <= d <= endDayi
中的任意一天 d
参加会议 i
。注意,一天只能参加一个会议。
请你返回你可以参加的 最大 会议数目。
示例 1:
输入:events = [[1,2],[2,3],[3,4]] 输出:3 解释:你可以参加所有的三个会议。 安排会议的一种方案如上图。 第 1 天参加第一个会议。 第 2 天参加第二个会议。 第 3 天参加第三个会议。
示例 2:
输入:events= [[1,2],[2,3],[3,4],[1,2]] 输出:4
提示:
1 <= events.length <= 105
events[i].length == 2
1 <= startDayi <= endDayi <= 105
原站题解
php 解法, 执行用时: 988 ms, 内存消耗: 142.5 MB, 提交时间: 2023-08-22 10:22:56
class Solution { /** * @param Integer[][] $events * @return Integer */ function maxEvents($events) { $stack1 = new SplMinHeap(); $stack2 = new SplMinHeap(); $cur = PHP_INT_MAX; foreach($events as $k=>$e){ $stack1->insert([$e[0],$e[1],$k]); $stack2->insert([$e[1],$e[0],$k]); $cur = min($cur,$e[0]); } $res = 0; $cache = []; while($stack2->isEmpty() === false && $stack1->isEmpty() === false){ $top1 = $stack1->top(); $top2 = $stack2->top(); //var_dump(json_encode($top1).";".json_encode($top2).";cur:$cur;res:$res;cache:".json_encode($cache)); if($top2[1] <= $cur && $top2[0] >= $cur){ //var_dump("if"); $stack2->extract(); if(isset($cache[$top2[2]]))continue; $cache[$top2[2]] = 1; $cur += 1; ++$res; }elseif($top1[0] <= $cur && $top1[1] >= $cur){ //var_dump("elseif"); $stack1->extract(); if(isset($cache[$top1[2]]))continue; $cache[$top1[2]] = 1; $cur += 1; ++$res; } while($stack1->isEmpty() === false && $stack1->top()[1] < $cur)$stack1->extract(); while($stack2->isEmpty() === false && $stack2->top()[0] < $cur)$stack2->extract(); if($stack1->isEmpty() || $stack2->isEmpty())break; if($cur < $stack1->top()[0]) $cur = $stack1->top()[0]; } return $res; } }
golang 解法, 执行用时: 300 ms, 内存消耗: 20 MB, 提交时间: 2023-08-22 10:18:38
// 在当前可以参加的会议中,使用堆去找最早到期的会议参加。 func maxEvents(events [][]int) int { sort.SliceStable(events, func(i,j int)bool{ return events[i][0] < events[j][0] }) h := hp{} count := 0 for time := 0; time < 1e5 + 1; time ++{ for len(events) > 0{ if time >= events[0][0]{ h.push(events[0][1]) events = events[1:] continue } break } for h.Len() > 0 && time > h.top(){ h.pop() } if h.Len() > 0 && time <= h.pop(){ count ++ } } return count } type hp struct{ sort.IntSlice } func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) } func (h *hp) Pop() interface{} { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v } func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] } func (h *hp) push(v int) { heap.Push(h, v) } func (h *hp) pop() int { return heap.Pop(h).(int) } func (h hp) empty() bool { return len(h.IntSlice) == 0 } func (h hp) top() int { return h.IntSlice[0] }
python3 解法, 执行用时: 420 ms, 内存消耗: 54.1 MB, 提交时间: 2023-08-22 10:17:28
class Solution: def maxEvents(self, events: List[List[int]]) -> int: ans, T = 0, 0 # 记录参加的会议数目,最大天数 # dic_evt[i]是列表,包含在第i天开始的会所有议的结束时间; T是总时间长度 dic_evt = defaultdict(list) for evt in events: dic_evt[evt[0]].append(evt[1]) T = max(T, evt[1]) # 对时间1~T遍历 每个时刻t,que_able保存当前可参加的会议的结束时间 que_able = [] for t in range(1, T+1): for end in dic_evt[t]: heapq.heappush(que_able, end) # pop结束时间小于t的会议 参加结束时间大于t的会议中结束时间最早的 while que_able and que_able[0] < t: heapq.heappop(que_able) # 此时que_able中都是结束时间大于t的会议所对应的结束时间 if que_able: ans += 1 heapq.heappop(que_able) return ans
cpp 解法, 执行用时: 456 ms, 内存消耗: 188.7 MB, 提交时间: 2023-08-22 10:14:46
/** * 扫描算法+贪心 * */ const int MAX = 1e5 + 1; class Solution { public: int maxEvents(vector<vector<int>>& events) { vector<vector<int>> left(MAX); for (int i = 0; i < events.size(); ++i) left[events[i][0]].emplace_back(i); int ans = 0; priority_queue<int, vector<int>, greater<>> pq; for (int i = 1; i < MAX; ++i) { for (int j : left[i]) pq.push(events[j][1]); while (!pq.empty() && pq.top() < i) pq.pop(); if (!pq.empty()) { pq.pop(); ans++; } } return ans; } };