Re: [闲聊] 每日leetcode

楼主: oin1104 (是oin的说)   2024-10-12 15:57:55
题目:
请问要把线段分成几组
他们才不会彼此重叠
思路:
想一下之后
可以发现其实只要知道他最多重叠几段就好了
所以用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;
}
};
```
作者: Furina (芙宁娜)   2024-10-12 15:58:00
我好崇拜你
作者: JIWP (JIWP)   2024-10-12 16:00:00
你有什么用
作者: mrsonic (typeB)   2024-10-12 16:02:00
要冲击四强了吗
作者: kirisan (一步抵三步)   2024-10-12 16:11:00
你有什么用

Links booklink

Contact Us: admin [ a t ] ucptt.com