普通扫描线
/**
* Definition of Interval:
* class Interval {
* public:
* int start, end;
* Interval(int start, int end) {
* this->start = start;
* this->end = end;
* }
* }
*/
class Solution {
public:
/**
* @param airplanes: An interval array
* @return: Count of airplanes are in the sky.
*/
int countOfAirplanes(vector<Interval> &airplanes) {
vector<pair<int,int>> ve;
for(auto x:airplanes) {
ve.push_back({x.start,1});
ve.push_back({x.end,-1});
}
sort(ve.begin(),ve.end(),[](pair<int,int> a,pair<int,int> b){
if(a.first==b.first)
return a.second<b.second;
return a.first<b.first;
}
);
int cnt=0;
int ans=0;
for(auto p:ve) {
if(p.second==1) cnt++;
else cnt--;
ans=max(ans,cnt);
}
return ans;
}
};
力扣 252会议室 (会员题)
按照开始时间排序,
然后遍历,如果有前一个的结束时间大于后一个的开始时间,那么返回假(正常情况下是,前一个的结束的时间要小于等于后一个的开始时间。)
最后,返回真
(无)
力扣 253会议室 (会员题)
题目:
给定一个会议时间安排的数组,
每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],…] (si < ei),
为避免会议冲突,同时要考虑充分利用会议室资源,请你计算至少需要多少间会议室,才能满足这些会议安排。
示例:
输入: [[0, 30],[5, 10],[15, 20]]
输出: 2
输入: [[7,10],[2,4]]
输出: 1
思路:
和之前的数飞机一样,找到最多的同时开的会议数量即可
(无)
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
// if(intervals.size()==0) return vector<vector<int>> (0);
sort(intervals.begin(),intervals.end());
vector<vector<int>> ve;
vector<int> res=intervals[0];
for(auto next:intervals){
if(res[1]>=next[0]) res[1]=max(res[1],next[1]);
else {
ve.push_back(res);
res=next;
}
}
ve.push_back(res);
return ve;
}
};
划分每一个x坐标相邻的区间 在上面对y坐标做区间合并 则此相邻区间面积为 所有 相邻区间长度*y坐标区间长度的和
时间复杂 O(n^2log(n)) 数据较大会超时
// Problem: P5490 【模板】扫描线
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5490
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define pll pair<ll,ll>
typedef long long ll;
const ll N=1e6+10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n;
pll L[N],R[N];
pll q[N];
ll range_area(ll a,ll b) {
ll cnt=0;
for(ll i=0;i<n;i++) {
if(L[i].x<=a&&R[i].x>=b)
q[cnt++]={L[i].y,R[i].y};
}
if(!cnt) return 0;
sort(q,q+cnt);
ll res=0;
ll st=q[0].x,ed=q[0].y;
for(ll i=1;i<cnt;i++) {
if(q[i].x<=ed) ed=max(ed,q[i].y);
else {
res+=ed-st;
st=q[i].x,ed=q[i].y;
}
}
res+=ed-st;
return res*(b-a);
}
void solve() {
cin>>n;
vector<ll> ve;
for(ll i=0;i<n;i++) {
cin>>L[i].x>>L[i].y>>R[i].x>>R[i].y;
ve.push_back(L[i].x);
ve.push_back(R[i].x);
}
sort(ve.begin(),ve.end());
ll res=0;
for(ll i=0;i+1<ve.size();i++) {
if(ve[i]!=ve[i+1]) {
res+=range_area(ve[i],ve[i+1]);
}
}
cout<<res<<endl;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll T=1;
//cin>>T;
while(T--) {
solve();
}
return 0;
}