推 Furina: 我好崇拜你 10/12 15:58
推 JIWP: 你有什麼用 10/12 16:00
推 mrsonic: 要衝擊四強了嗎 10/12 16:02
→ kirisan: 你有什麼用 10/12 16:11
題目:
請問要把線段分成幾組
他們才不會彼此重疊
思路:
想一下之後
可以發現其實只要知道他最多重疊幾段就好了
所以用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