1353 Maximum Number of Events That Can Be Attended 最多可以參加的會議數(shù)目
Description:
You are given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.
You can attend an event i at any day d where startTimei <= d <= endTimei. You can only attend one event at any time d.
Return the maximum number of events you can attend.
Example:
Example 1:
[圖片上傳失敗...(image-644eea-1666361299596)]
Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.
Example 2:
Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4
Constraints:
1 <= events.length <= 10^5
events[i].length == 2
1 <= startDayi <= endDayi <= 10^5
題目描述：
給你一個(gè)數(shù)組 events亿乳，其中 events[i] = [startDayi, endDayi] 薄啥，表示會議 i 開始于 startDayi 讼昆，結(jié)束于 endDayi 。
你可以在滿足 startDayi <= d <= endDayi 中的任意一天 d 參加會議 i 脖含。注意比规，一天只能參加一個(gè)會議守屉。
請你返回你可以參加的 最大 會議數(shù)目。
示例：
示例 1：
[圖片上傳失敗...(image-6813c5-1666361299597)]
輸入：events = [[1,2],[2,3],[3,4]]
輸出：3
解釋：你可以參加所有的三個(gè)會議夷野。
安排會議的一種方案如上圖懊蒸。
第 1 天參加第一個(gè)會議。
第 2 天參加第二個(gè)會議悯搔。
第 3 天參加第三個(gè)會議骑丸。
示例 2：
輸入：events= [[1,2],[2,3],[3,4],[1,2]]
輸出：4
提示：
1 <= events.length <= 10^5
events[i].length == 2
1 <= startDayi <= endDayi <= 10^5
思路：
掃描線 ? 優(yōu)先隊(duì)列
按照開始時(shí)間將對應(yīng)下標(biāo)加入
對于每個(gè)開始時(shí)間將對應(yīng)結(jié)束時(shí)間加入小根堆
將所有不合法的結(jié)束時(shí)間都彈出, 然后如果小根堆不為空, 彈出一個(gè)時(shí)間, 該會議可以參加
時(shí)間復(fù)雜度為 O(slgn), 空間復(fù)雜度為 O(s), 其中 s 表示最大的結(jié)束時(shí)間
代碼:
C++:
class Solution
{
public:
int maxEvents(vector<vector<int>>& events)
{
vector<vector<int>> starts(100010);
int result = 0, n = events.size();
for (int i = 0; i < n; i++) starts[events[i].front()].emplace_back(i);
priority_queue<int> pq;
for (int i = 1; i < 100010; i++)
{
for (int j : starts[i]) pq.push(-events[j].back());
while (!pq.empty() and -pq.top() < i) pq.pop();
if (!pq.empty())
{
pq.pop();
++result;
}
}
return result;
}
};
Java:
class Solution {
public int maxEvents(int[][] events) {
List<List<Integer>> starts = new ArrayList<>(100010);
int m = 0, result = 0, n = events.length;
for (int i = 0; i < n; i++) m = Math.max(m, events[i][1]);
for (int i = 0; i <= m; i++) starts.add(new ArrayList<>());
for (int i = 0; i < n; i++) starts.get(events[i][0]).add(i);
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 1; i <= m; i++) {
for (int j : starts.get(i)) pq.offer(events[j][1]);
while (!pq.isEmpty() && pq.peek() < i) pq.poll();
if (!pq.isEmpty()) {
pq.poll();
++result;
}
}
return result;
}
}
Python:
class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
n, starts, heap, result, m = len(events), defaultdict(list), [], 0, max(e for s, e in events)
for i in range(n):
starts[events[i][0]].append(i)
for i in range(1, m + 1):
for j in starts[i]:
heappush(heap, events[j][1])
while heap and heap[0] < i:
heappop(heap)
if heap:
heappop(heap)
result += 1
return result
