AcWing1750.救生員
題目鏈接
題目描述
農夫約翰為他的牛開設了一個游泳池，他認為這將幫助它們放松并產出更多的奶，
為了確保安全，他雇傭了 N 頭奶牛作為救生員，每頭奶牛的作業班次都是一段連續的時間，
為了簡單起見，游泳池每天的開放時間從時刻 0 到時刻 1000，
每個奶牛的作業班次都可以用兩個整數來描述，它們分別表示該奶牛作業班次的開始時刻和結束時刻，
例如，從時刻 t=4 開始作業并在時刻 t=7 結束作業的救生員，它的作業時間為三個時間單位（請注意，時間“段”兩端的端點是時間軸上的“點”），
不幸的是，由于資金緊張問題，約翰不得不解雇一頭奶牛，
請問通過合理裁員，剩余救生員的作業班次仍然可以覆寫的最大時間有多長？
一個時間間隔內如果存在至少一名救生員當值，那么這個時間間隔就認為是被覆寫的，
輸入格式
第一行包含整數 N，
接下來 N 行，每行描述一個救生員的作業班次，包含兩個整數，表示一個救生員的開始作業時刻和結束作業時刻，
所有時刻各不相同，不同救生員的作業班次可能有覆寫，
輸出格式
輸出一個整數，表示解雇掉一頭奶牛后，剩余救生員的作業班次仍然可以覆寫的最長時間，
資料范圍
1≤N≤100
0≤開始時刻≤結束時刻≤1000
輸入樣例：
3
5 9
1 4
3 7
輸出樣例：
7
解題思路
本題可以使用區間合并的方法求解，不做過多贅述，上代碼，
代碼：
#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
int n;
pair<int,int> cow[105];
int res;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>cow[i].first>>cow[i].second;
sort(cow,cow+n);
for(int i=0;i<n;i++)
{
int sum=0;
int start=-1,end=-1;
for(int j=0;j<n;j++)
if(i!=j)
{
if(cow[j].first<=end) //當前區間起點小于上一區間終點，則合并區間
end=max(cow[j].second,end); //取終點值較大的作為合并后區間的終點
else
{
sum+=end-start; //將前一個區間的大小進行累加
start=cow[j].first; //當前區間的起點成為新起點
end=cow[j].second; //當前區間的終點成為新終點
}
}
sum+=end-start; //對最后一個區間長度進行累加
res=max(res,sum); //對區間覆寫最大長度進行更新
}
cout<<res<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/423378.html
標籤：其他
上一篇：人工智能與智能系統2-> 機器人學2 | 時間與運動
下一篇：裴蜀定理