1323: [example 6.5] activity selection

 

1323：【 example 6.5】 Activity selection

The time limit : 1000 ms         Memory limit : 65536 KB
Submission number : 15984     Passing number : 8866

【 Title Description 】

The school is open in recent days nn An activity , These activities need to use the school auditorium , At the same time , The auditorium can only be used by one activity . Because of the time conflict in some activities , School office staff had to let some activities abandon the use of the auditorium and use other classrooms .

Now give nn The starting time of using the auditorium for an activity beginibegini And end time endi(begini<endi)endi(begini<endi), Please help the office staff arrange some activities to use the auditorium , Ask to arrange as many activities as possible .

【 Input 】

The first line is an integer n(n≤1000)n(n≤1000);

Next nn That's ok , Two integers per line , first beginibegini, The second is endi(begini<endi≤32767)endi(begini<endi≤32767).

【 Output 】

Output the maximum number of activities that can be arranged .

【 sample input 】

11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13

【 sample output 】

4

【 Algorithm analysis 】

Algorithm model ： to n An open interval （begini,endi）, Choose as many intervals as possible , Make two not pay .

practice ： First of all, in accordance with the end1<=end2<=...<=endn The order of , Consider each activity in turn , If there is no conflict with the selected activity , Just choose ; Otherwise, you don't choose .

correctness ： If you don't choose end1, Suppose the first choice is endi, If endi and end1 If it doesn't intersect, choose one more end1 More cost effective ; If it crosses, turn endi Switch to end1 Does not affect subsequent choices .

【CE Code 】

#include<iostream>
using namespace std;
const int N=2e3;
inline int fread()
{
	char ch=getchar();
	int n=0,m=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-')m=-1;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
	return n*m;
}
void fwrite(int n)
{
	if(n>9)fwrite(n/10);
	putchar(n%10+'0');
}
int n,begin[N],end[N];
void init()
{
	n=fread();
	for(int i=1;i<=n;i++)begin[i]=fread(),end[i]=fread();
}
void qsort(int m,int x)
{
	int i=m,j=x,mid=end[m+x>>1];
	while(i<=j)
	{
		while(end[i]<mid)i++;
		while(end[j]>mid)j--;
		if(i<=j)swap(end[i],end[j]),swap(begin[i],begin[j]),i++,j--;
	}
	if(m<j)qsort(m,j);
	if(i<x)qsort(i,x);
}
void f()
{
	int ans=0;
	for(int i=1,j=-1;i<=n;i++)
		if(begin[i]>=j)ans++,j=end[i];
	fwrite(ans);
}
signed main()
{
	init(),qsort(1,n),f();	
	return 0;
}

Pay attention to it

 

#include<stdio.h>
#include<iostream>
using namespace std;
const int N=2e3;
inline int fread()
{
	char ch=getchar();
	int n=0,m=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-')m=-1;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
	return n*m;
}
void fwrite(int n)
{
	if(n>9)fwrite(n/10);
	putchar(n%10+'0');
}
int n,begin[N],end[N];
void init()
{
	n=fread();
	for(int i=1;i<=n;i++)begin[i]=fread(),end[i]=fread();
}
void qsort(int m,int x)
{
	int i=m,j=x,mid=end[m+x>>1];
	while(i<=j)
	{
		while(end[i]<mid)i++;
		while(end[j]>mid)j--;
		if(i<=j)swap(end[i],end[j]),swap(begin[i],begin[j]),i++,j--;
	}
	if(m<j)qsort(m,j);
	if(i<x)qsort(i,x);
}
void f()
{
	int ans=0;
	for(int i=1,j=-1;i<=n;i++)
		if(begin[i]>=j)ans++,j=end[i];
	fwrite(ans);
}
signed main()
{
	init(),qsort(1,n),f();	
	return 0;
}

Pay attention to it

 

#include<bits/stdc++.h>
using namespace std;
const int N=2e3;
inline int fread()
{
	char ch=getchar();
	int n=0,m=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-')m=-1;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
	return n*m;
}
void fwrite(int n)
{
	if(n>9)fwrite(n/10);
	putchar(n%10+'0');
}
int n,begin[N],end[N];
void init()
{
	n=fread();
	for(int i=1;i<=n;i++)begin[i]=fread(),end[i]=fread();
}
void qsort(int m,int x)
{
	int i=m,j=x,mid=end[m+x>>1];
	while(i<=j)
	{
		while(end[i]<mid)i++;
		while(end[j]>mid)j--;
		if(i<=j)swap(end[i],end[j]),swap(begin[i],begin[j]),i++,j--;
	}
	if(m<j)qsort(m,j);
	if(i<x)qsort(i,x);
}
void f()
{
	int ans=0;
	for(int i=1,j=-1;i<=n;i++)
		if(begin[i]>=j)ans++,j=end[i];
	fwrite(ans);
}
signed main()
{
	init(),qsort(1,n),f();	
	return 0;
}

Pay attention to it

 

#include<iostream>
using namespace std;
int n,begin[1001],end[1001];
void init()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>begin[i]>>end[i];
}
void qsort(int x,int y)
{
	int i,j,mid,t;
	i=x;j=y;mid=end[(x+y)/2];
	while(i<=j)
	{
		while(end[i]<mid)i++;
		while(end[j]>mid)j--;
		if(i<=j)
		{
			t=end[j];end[j]=end[i];end[i]=t;
			t=begin[j];begin[j]=begin[i];begin[i]=t;
			i++;j--;
		}
	}
	if(x<j) qsort(x,j);
	if(i<y) qsort(i,y);
}
void solve()
{
	int ans=0;
	for(int i=1,t=-1;i<=n;i++)		// While initializing the loop variable , initialization  t
	 if(begin[i]>=t) {ans++;t=end[i];} 
	 				// If the current activity does not conflict with the last activity before , Just accept the current activity 
	cout<<ans<<endl; 
}
int main()
{
	init();
	qsort(1,n);
	solve();
	return 0;
}

Pay attention to it

【AC Code 】

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct meet{
	int begin;
	int end;
	friend bool operator <(meet a,meet b){
		return a.end<b.end;
	}
}me[1005];
int main(int argc, char *argv[])
{
	int n,sum=1;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d %d",&me[i].begin,&me[i].end);
	sort(me,me+n);
	int l=me[0].begin,r=me[0].end;
	for(int i=1;i<n;i++){
		if(me[i].begin>=r){
			l=me[i].begin;
			r=me[i].end;
			sum++;
		}
	}
	printf("%d\n",sum);
	return 0;
}

  This question is all Fucking Toxic .

Pay attention to it