Re: [閒聊] 每日leetcode
題目:
請問要把線段分成幾組
他們才不會彼此重疊
思路:
想一下之後
可以發現其實只要知道他最多重疊幾段就好了
所以用pq來遍歷他們的開頭跟結尾
因為開頭要先遍歷 所以用-1
結尾用1
加的時候用-=就好了
```cpp
class Solution {
public:
int minGroups(vector<vector<int>>& intervals)
{
int n = intervals.size();
priority_queue<pair<int,int> , vector<pair<int,int>> , greater<pair<int,
int>>> in;
for(int i = 0 ; i < n ; i ++)
{
int l = intervals[i][0];
int r = intervals[i][1];
in.push({l,-1});
in.push({r,1});
}
int res = 0;
int overlay = 0;
while(!in.empty())
{
int now = in.top().first;
overlay -= in.top().second;
in.pop();
res = max(overlay , res);
while(!in.empty() && now >= in.top().first)
{
overlay -= in.top().second;
in.pop();
res = max(overlay , res);
}
}
return res;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.19.26 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728719877.A.A7F.html
推
10/12 15:58,
1年前
, 1F
10/12 15:58, 1F
推
10/12 16:00,
1年前
, 2F
10/12 16:00, 2F
推
10/12 16:02,
1年前
, 3F
10/12 16:02, 3F
→
10/12 16:11,
1年前
, 4F
10/12 16:11, 4F
討論串 (同標題文章)
完整討論串 (本文為第 978 之 1554 篇)：