做任務(wù)三?

?

wwwwodddd?(命題人)

基準(zhǔn)時間限制：1?秒 空間限制：131072?KB 分值:?5

B君和m個人一起，要完成n個任務(wù)，在這個題中，B君和m個人，什么都不做。

第i個任務(wù)有一個開始時間s[i]和結(jié)束時間e[i]（保證s[i]<=e[i]），一個人完成兩個任務(wù)的時間區(qū)間，不能有交集，但是可以首尾相連。（參考樣例）

換句話說，如果一個人依次完成了(s[1], e[1]) (s[2], e[2]) (s[3], e[3])這3個任務(wù)，那么這3個任務(wù)需要滿足s[1]<=e[1]<=s[2]<=e[2]<=s[3]<=e[3]。

同一個任務(wù)只能完成一次，并且中間不能換人。

B君和m個人，想知道要想完成這些任務(wù)，至少需要幾個人？

(單組 n <= 100000)

(所有 n 求和 <= 200000)

(開始時間和結(jié)束時間，都是非負(fù)整數(shù)，且在int范圍內(nèi)。)

(開始時間 <= 結(jié)束時間，如果等于的話，意味著這個任務(wù)可以瞬間被做完，但是不能沒有人做)

Input

多組數(shù)據(jù)，第一行是數(shù)據(jù)組數(shù)。 每組數(shù)據(jù)的第一行兩個整數(shù)n,?m分別表示任務(wù)數(shù)，和人數(shù)。 以下n行，每行兩個整數(shù)表示任務(wù)的開始時間和結(jié)束時間。

Output

對于每組數(shù)據(jù)輸出一個整數(shù) 表示完成這些任務(wù)至少需要多少人。

Input示例

4 2?1 1?3 2?4 2?1 1?3 3?5 2?1 1?3 2?2 4?1 1?2 2?2 2?2 2?3

Output示例

2 1 2 1

本題問你最少需要多少個人來完成這些任務(wù)，這也是區(qū)間不相容的一個延伸。

做法一：

區(qū)間按照結(jié)束時間排序，如果一個任務(wù)能做，那么就讓最晚結(jié)束的那個人去做，如果不能做就在加一個人去做。

代碼就不貼了，因為這個方法我沒有寫代碼。

做法二：

區(qū)間按照開始時間排序，如果一個任務(wù)能做，那么就讓最早結(jié)束的那個人去做。每次更新時間的時候，隊列中都要彈出最早結(jié)束的那個人（這個人可以去做下一個能做任務(wù)了。）

如果不能做就在加一個人去做。可以用優(yōu)先隊列（小根堆）去保存結(jié)束時間。

AC代碼：

#include <cstdio> #include <iostream> #include <cstdlib> #include <cstring> #include <algorithm> #include <queue> #include <map> using namespace std; pair<int,int>a[100001]; int main() {int t;scanf("%d",&t);while(t--){priority_queue<int>q;int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%d%d",&a[i].first,&a[i].second);sort(a,a+n);//默認(rèn)開始時間排序int sum=0;for(int i=0;i<n;i++){if(q.size()&&-q.top()<=a[i].first)//結(jié)束時間小于開始時間，每次都找結(jié)束時間最早的那個人去做 {q.pop();//彈出這個人的結(jié)束時間q.push(-a[i].second);//加新的結(jié)束時間進(jìn)去//此時這些任務(wù)都是一個人在做}else//不能做{q.push(-a[i].second);//加一個人并且把它的結(jié)束時間加進(jìn)去sum++;}}printf("%d\n",sum);}return 0; }

這個題也可以用priority_queue<int,vector<int>,greater<int> >q;

那么問題來了，怎么確定那個任務(wù)是第幾個人做的呢？

請點擊：

https://blog.csdn.net/qq_42217376/article/details/81165404

今天做了些題，發(fā)現(xiàn)好多貪心題都可以用STL來解決，漲知識了。

轉(zhuǎn)載于:https://www.cnblogs.com/zut-syp/p/10543747.html

總結(jié)

以上是生活随笔為你收集整理的E 做任务三（区间）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。