题解

先将活动结束时间排序，再依次判断活动能否举办，注意cnt一开始要为1

代码

#include<bits/stdc++.h>
using namespace std;
struct sum{
	int a,b;
}suum[1005]; 
bool cmp(sum x,sum y){
	return x.b<y.b;
}
int main()
{
	int n,cnt=1,i=0,j=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d %d",&suum[i].a,&suum[i].b);
	}
	sort(suum,suum+n,cmp);
	for(i=1;i<n;i++)
	{
		if(suum[i].a>=suum[j].b)
		{
			j=i;
			cnt++;
		}
	}
	printf("%d",cnt);
	return 0;
}

题解

这个题还是很简单的，合理分配时间，尽量让多的活动可以做到“无缝衔接”，自然就是上一个活动结束发刚好可以让下一个活动开始就是最佳利用时间，解题思路基本也就出来了，将结束时间按照先后顺序进行排序，然后以第一个活动为基准，一次链接后面可以“顺位”——开始时间在上一个结束时间之后或者相同，这样就可以达到合理分配时间的效果，上代码：

代码

#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
int x[100000000];
struct Main{
	int kai;
	int jie;
}pp[1001];
int cmp(Main x,Main y){
	return x.jie<y.jie;
}
int main()
{
	int n,tong=1;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>pp[i].kai>>pp[i].jie;
	}
	sort(pp+1,pp+n+1,cmp);
	int lian=1;
	for(int i=2;i<=n;i++){
		if(pp[i].kai>=pp[lian].jie){
			tong++;
			lian=i;
		}
	}
	cout<<tong<<endl; 
	return 0;
}

题目解析：

很明显是贪心，从最早的活动结束时间作为标准，向后逐个比较每个活动的开始时间，如果冲突就继续比较下一个，如果不冲突就计数加1，且将此不冲突活动的结束时间作为标准继续向后比较，直到所有活动都比较完。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef struct {
	int s;
	int f;
}activity;
activity a[1010];
bool cmp(activity a, activity b) {
	return a.f < b.f;
}
 
int main(){
    int n,t = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
    	cin >> a[i].s >> a[i].f;
	}
	sort(a + 1, a + n + 1, cmp);
	int min = 1;	//最小结束时间的下标 
	for (int i = 2; i <= n; i++) {	//逐个进行判断下一个活动的开始时间是否与本次活动的结束时间冲突 
		if(a[i].s >= a[min].f) {	//不冲突就计数器加1且最小结束时间下标转移 
			t++;
			min = i;
		}
	}
	cout << t + 1;
    return 0;
}

题解

这道题呢，需要找出时间不冲突的最多活动数，对活动结束时间进行排序，然后判断前一个活动的结束时间是不是小于后一个活动的开始时间。在排序中就已经确定了第一个活动，所以计数的时候从1开始，注意记录下一个活动的下标。

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
	int b,e;
}a[1005];
bool com(node a,node b){
	return a.e<b.e;
}
int main(){
	std::ios::sync_with_stdio(false);
    int n,sum=1,ll=0;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i].b>>a[i].e;
    sort(a,a+n,com);
	for(int i=1;i<n;i++){
		if(a[i].b>=a[ll].e){
			ll=i;
			sum++;
		}
	}
	cout<<sum<<endl;
    return 0;
}

这题应该挺经典，这是本小白第二次看见他了（虽然还是错了QAQ）

我们可以这么看，我们已知的是一段段间距，其分别对应一个开始坐标，和一个结束坐标,其分别在时间轴上占据了一个点，求这个时间轴上最多可容纳的间断数。

成语“有始有终”，每个间断必定有一个终点。我们以终点为标准排序，此操作的目的是为求最多。

然后接着我们要做的就是筛选了，以0为基点，用段起点来判断是否满足条件，逐一更新，满足条件的段的终点就是下个段可开始的基点

    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    struct node{
    	int e,b;
    }a[1003];
    int cmp(node x,node y)
    {
    	return x.e < y.e;
    }
    int main()
    {
    	int n,ans = 0;
    	scanf("%d",&n);
    	for(int i = 1;i <= n;i++)
    	{
    		scanf("%d%d",&a[i].b,&a[i].e);
    	}
    	sort(a + 1,a + n + 1,cmp); 
    	int t = 0;
    	for(int i = 1;i <= n;i++)
    	{
    		if(a[i].b >= t)
    		{
    			ans++;
    			t = a[i].e;
    		}
    	}
    	printf("%d",ans);
    	return 0;	
    }

P1087. 「一本通 1.1 例 1」活动安排 —— 贪心算法

题意概述

给定多个活动，每个活动有自己的开始时间和结束时间，每个活动的占用同一资源，也就是说，活动时间不可发生重叠。 再翻译一下就是，前一个活动的结束必须早与后一个活动的开始时间。

题意分析

这里很多时候我们会直接去想着用开始时间排序，然后再把开始时间相同的活动安结束时间再排序，最后再比较判断（我试了，好像不行） 好我们来看看使用贪心的思维怎么去解这个题，我们这里要反过来想，是否可以按照结束时间排序。没错就是按照结束时间从小到大排序，就可以避免对每个活动的时长的考虑。排序完后的结果再按照前一个活动的结束时间必须小于后一个活动的开始时间来挑选活动。

1. 将每个活动以结束时间为关键字排序
2. 按照题意挑选活动

可行代码

#include <algorithm>
#include <iostream>
using namespace std;

struct aa {
    int start;
    int end;
};

bool cmp(aa x, aa y) { return x.end <= y.end; }

void greedychoose(int n, aa a[]) {
    int s = 1, i = 1;
    for (int j = 2; j <= n; j++) {
        if (a[j].start >= a[i].end) {
            i = j;
            s++;
        }
    }
    cout << s << endl;
}

int main() {
    int n, i = 1;
    cin >> n;
    aa time[n + 5];
    while (i <= n) {
        cin >> time[i].start >> time[i].end;
        i++;
    }
    sort(time + 1, time + n, cmp);
    greedychoose(n, time);
}

这道题首先我们要得到最多能够开展多少活动，我的想法是将每个活动的时间以右边界为标准，按升序来排序，根据贪心的思想，我肯定得优先选择右边界最小的，然后从右边界最小的里面来匹配，看此时他的左边界是否符合要求，并且计数
不多说 来看代码：

#include <bits/stdc++.h>
using namespace std;
pair<int,int>pa[1005];
bool cmp(pair<int,int>a,pair<int,int>b)
{
	return a.second<b.second;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>pa[i].first>>pa[i].second;
	}
	sort(pa+1,pa+n+1,cmp);
	int cnt = 1;
	int r = pa[1].second;//先确定最小的右边界
	for(int i=1;i<=n;++i)
	{
		if(pa[i].first>=r){
			cnt++;
			r=pa[i].second;//每次匹配成功，将cnt++并且更新新的右边界
		}
	}
	cout << cnt << endl;
}

分析: 创建一个集合结构体，储存开始时间与结束时间。将结构体进行从小到大进行排序，然后将第一次结束时间拿出来，从第二个元素开始循环比较，如果开始时间大于结束时间就++，更新结束时间 代码: #include #include #include using namespace std; struct set{ int s; int f; bool operator<(const set &rhs)const{ return f<rhs.f; } }; int main() { int n; set a[1005]; memset(a,0,sizeof(a)); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].s,&a[i].f); } sort(a+1,a+1+n); int ans=1; int cnt=a[1].f; for(int i=2;i<=n;i++) { if(a[i].s>=cnt) { ans++; cnt=a[i].f; } } printf("%d",ans); return 0; }