- 來(lái)源:L2-055 胖達(dá)的山頭-Pintia
- 題意:給定 \(n\) 個(gè)事件的起始和終止時(shí)刻(以
hh:mm:ss給出),求最多并行事件數(shù)。
- 關(guān)鍵詞:差分(簽到,模板題)
- 題解:將所有時(shí)刻轉(zhuǎn)換為秒,當(dāng)某事件開(kāi)始+1,結(jié)束則-1。按時(shí)間排序,因此問(wèn)題轉(zhuǎn)換為一維差分,求原數(shù)組后輸出最大值即可。
- 代碼:
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
int sec(string s){
int h=(s[0]-'0')*10+(s[1]-'0');
int m=(s[3]-'0')*10+(s[4]-'0');
int sec=(s[6]-'0')*10+(s[7]-'0');
return h*3600+m*60+sec;
}
void solve(){
int n;cin>>n;
vector<pii>v;
for(int i=0;i<n;i++){
string a,b;cin>>a>>b;
v.push_back({sec(a),1}),v.push_back({sec(b)+1,-1});
}
sort(v.begin(),v.end());
int now=0,ans=0;
for(auto i:v) now+=i.se,ans=max(ans,now);
cout<<ans<<'\n';
}
int main() {
ios::sync_with_stdio(0),cin.tie(0);
solve();
return 0;
}