(2022 Hangdian multi school III) 1009.package delivery (greedy)

subject ：

  The sample input ：

1
4 2
1 3
2 4
6 7
4 7

Sample output ：

2

The question ： Multiple tests , For each set of tests , Give me a n and k,n Represents the number of express delivery ,k Represents the maximum number of express deliveries we can get at one time , Next n Each line gives two numbers , Respectively represents the arrival time and deadline of express , We have to pick up the express before the deadline , You can get multiple express deliveries in a day , Ask us how many times we need to pick up all express delivery at least .

analysis ： This is obviously a greedy problem , Since there is no limit to the number of times you can pick up express delivery in a day , Then we can try to postpone the time of picking up the express , In this way, our express delivery number will be more and more , Accordingly, the number of express deliveries taken out at one time may also be more , We only pick up express delivery at the deadline , We should pick up as many express deliveries as possible at one time , First of all, we need to follow l Ascending order , Then traverse from front to back , We can set a time t Represents our current time point , We use a queue to record the express that has arrived at the current time and has not been taken out , Then all l<t All express deliveries should be added to the queue （ The express that hasn't been taken out ）, This queue follows r Ascending order , Because when t Equal to the deadline of an express delivery, we must take it out once .

When t There are two situations for the number of couriers in the queue when the deadline for a courier arrives ：

（1） Less than or equal to k individual , Then we can take it out directly

（2） Greater than k individual , Then we will r Arrive and take out from childhood k Just one （ Even if it's not finished, just take k individual ）

The reason why the number of express delivery is greater than k The reason why we didn't take it all in one hour was that we took the urgent express delivery first , Then if the remaining Express has not arrived at the deadline , We can wait a little , Maybe you can take it out with other later express delivery , The answer may be better

This is the greedy strategy of this topic , See code for details ：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=400010;
typedef pair<int,int> PII;
int l[N],r[N];
struct node{
	int l,r;
}p[N];
bool cmp(node a,node b)
{
	return a.l<b.l;
}
void solve()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&p[i].l,&p[i].r);
	sort(p+1,p+n+1,cmp);
	priority_queue<PII,vector<PII>,greater<PII> >q;
	while(!q.empty()) q.pop();
	q.push({p[1].r,p[1].l});// First put r You can avoid handwriting sorting functions  
	int t=p[1].r,ans=0;
	for(int i=2;i<=n;)
	{
		while(i<=n&&(p[i].l<=t||t==-1))
		{
			if(t==-1) t=p[i].r;
			t=min(t,p[i].r);
			q.push({p[i].r,p[i].l});
			i++;
		}
		if(!q.empty())
		{
			ans++;
			if(q.size()<=k)
			{
				while(!q.empty())	q.pop();
				t=-1;
			}
			else
			{
				int tt=k;
				while(tt--)	  q.pop();
				t=q.top().first;
			}
		}
	}
	ans+=(q.size()+k-1)/k;// Finally, don't forget to take out all express delivery  
	printf("%d\n",ans);	
}
int main()
{
	int _;
	cin>>_;
	while(_--) solve();
	return 0;
}