題目:
請問要把線段分成幾組
他們才不會彼此重疊
思路:
想一下之後
可以發現其實只要知道他最多重疊幾段就好了
所以用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;
}
};
```