文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 錯(cuò)誤解
    • 2.2 超時(shí)解
    • 2.3 通過解
    • 2.4 大佬解

1. 題目

給你一個(gè)數(shù)組 events，其中 events[i] = [startDayi, endDayi] ，表示會(huì)議 i 開始于 startDayi ，結(jié)束于 endDayi 。

你可以在滿足 startDayi <= d <= endDayi 中的任意一天 d 參加會(huì)議 i 。注意，一天只能參加一個(gè)會(huì)議。

請(qǐng)你返回你可以參加的 最大 會(huì)議數(shù)目。

示例1： 輸入：events = [[1,2],[2,3],[3,4]] 輸出：3 解釋：你可以參加所有的三個(gè)會(huì)議。 安排會(huì)議的一種方案如上圖。 第 1 天參加第一個(gè)會(huì)議。 第 2 天參加第二個(gè)會(huì)議。 第 3 天參加第三個(gè)會(huì)議。示例 2：: 輸入：events= [[1,2],[2,3],[3,4],[1,2]] 輸出：4示例 3： 輸入：events = [[1,4],[4,4],[2,2],[3,4],[1,1]] 輸出：4示例 4： 輸入：events = [[1,100000]] 輸出：1示例 5： 輸入：events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]] 輸出：7提示： 1 <= events.length <= 10^5 events[i].length == 2 1 <= events[i][0] <= events[i][1] <= 10^5

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-number-of-events-that-can-be-attended
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

2.1 錯(cuò)誤解

• 先按會(huì)議的start排序，相同的話按照end排序

class Solution {//出錯(cuò)代碼 public:int maxEvents(vector<vector<int>>& events) {sort(events.begin(), events.end(),[](const auto& a, const auto& b){if(a[0] == b[0])return a[1] < b[1];return a[0] < b[0];});int i, count = 0, attendTime = 0;for(i = 0; i < events.size(); ++i){if(attendTime < events[i][0]){attendTime = events[i][0];count++;}else if(attendTime < events[i][1]){attendTime = attendTime+1;count++;}}return count;} };

根據(jù)出錯(cuò)的例子，可知上面算法有缺陷：
正確的應(yīng)該是：

• 對(duì)當(dāng)前會(huì)議i，還需要往下找到j(luò)，j 被包含在i的區(qū)間內(nèi)
• 如果attendTime與區(qū)間j有交點(diǎn)，優(yōu)先先參加j
  

2.2 超時(shí)解

class Solution {//超時(shí)代碼 public:int maxEvents(vector<vector<int>>& events) {sort(events.begin(), events.end(),[](vector<int>& a, vector<int>& b){if(a[0] == b[0])return a[1] < b[1];return a[0] < b[0];});int i, j, count = 0, attendTime = 0;for(i = 0; i < events.size(); ++i){if(attendTime < events[i][0]){attendTime = events[i][0];count++;attendTime++;}else if(attendTime <= events[i][1]){for(j = i+1; j < events.size() && events[i][1] <= events[j][1]; ++j);if(j < events.size() && attendTime >= events[j][0]){count++;events.erase(events.begin()+j);attendTime++;i--;continue;}count++;attendTime++;}}return count;} };

不幸的是：最后一個(gè)例子超時(shí)

2.3 通過解

優(yōu)化

• 當(dāng)attendTime與events[j]沒有交點(diǎn)時(shí)，提前break

class Solution {//通過代碼 public:int maxEvents(vector<vector<int>>& events) {sort(events.begin(), events.end(),[](vector<int>& a, vector<int>& b){if(a[0] == b[0])return a[1] < b[1];return a[0] < b[0];});int i, j, count = 0, attendTime = 0;for(i = 0; i < events.size(); ++i){if(attendTime < events[i][0]){attendTime = events[i][0];count++;attendTime++;//下一個(gè)可參加的時(shí)間}else if(attendTime <= events[i][1])//參加時(shí)間在區(qū)間內(nèi){for(j = i+1; j < events.size() && events[i][1] <= events[j][1]; ++j){ //向下查找，被i包含的區(qū)間jif(attendTime < events[j][0])break;//如果與attendTime沒有交點(diǎn)，后面都不可能有}if(j < events.size() && attendTime >= events[j][0]){ //如果有交點(diǎn)，優(yōu)先參加jcount++;events.erase(events.begin()+j);//參加了，刪除掉attendTime++;//下一個(gè)可能的參會(huì)時(shí)間點(diǎn)i--;//后面會(huì)i++，先--i,繼續(xù)跳轉(zhuǎn)到原來(lái)的i進(jìn)行處理continue;}count++;//attendTime與j沒有交點(diǎn)，參加會(huì)議 iattendTime++;//時(shí)間點(diǎn)往后挪一個(gè)}}return count;} };

2.4 大佬解

大佬的思路

• 按照會(huì)議start對(duì) events 升序排序
• 按日期time進(jìn)行掃描
• 將time時(shí)開始的會(huì)議都加入到優(yōu)先隊(duì)列（隊(duì)列存儲(chǔ)的是會(huì)議結(jié)束end時(shí)間）
• 優(yōu)先隊(duì)列（小頂堆）把結(jié)束日期早的先出隊(duì)，參加該會(huì)議
• time++，新的一天，先把優(yōu)先隊(duì)列里已經(jīng)過期的會(huì)議刪除

class Solution { public:int maxEvents(vector<vector<int>>& events) {sort(events.begin(), events.end());priority_queue<int,vector<int>, greater<int>> q;//小頂堆，結(jié)束時(shí)間早的，先出隊(duì)int count = 0, i = 0, time = 0;while(i < events.size() || !q.empty()){time++;while(!q.empty() && q.top() < time)//結(jié)束時(shí)間過去了，該會(huì)議刪除q.pop();while(i < events.size() && events[i][0] == time){q.push(events[i][1]);//time時(shí)間，會(huì)議i開始了，把他的結(jié)束時(shí)間push進(jìn)去i++;}if(!q.empty()){count++;q.pop();//最早結(jié)束的先參加}}return count;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1353. 最多可以参加的会议数目（排序+贪心，优先队列，难）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。