高质量题解|活动安排

题目大意

记录下每次的开始时间和结束时间，定义一开始的可参加活动数量和最后的结束时间，判断能否参加活动

考纲知识点

输入输出、分支结构、算术运算符、结构体基础、结构体排序、自定义函数、基础数据类型、变量的定义以及使用

数据范围

$1$ $≤$ $n$ $≤$ $1000$,$0$ $<$ $s$ $<$ $e$ $<$ $10^9$

解题思路

起始时间和终止时间可以记录在结构体 $node$ 中，记作起始时间 $s$ 和终止时间 $e$
将结束时间从小到大进行排序
定义一个变量 $last$ 用来记录当前活动的结束时间，因为前面已经排序了，所以从 $0$ 开始
定义一个变量 $num$ 记录可以参加的活动数量，因为无论怎么样我们的第一个活动都是可以参加的，所以变量从 $1$ 开始
同上，第一个无论怎样都可以参加，所以循环从 $1$ 开始
如果下一次的开始时间大于上一次 $last$ 的结束时间，可参加的活动数量增加，$last$ 重新定义为当前活动的结束时间

参考程序

#include <bits/stdc++.h>
using namespace std;
struct node{
	int s,e;
}a[1001];
bool cmp(node x,node y){
	//结束时间，从小到大
	return x.e < y.e; 
}
int main(){
	int n;
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> a[i].s >> a[i].e;
	}
	sort(a,a + n,cmp);
	int last = a[0].e;//last:记录当前活动的结束时间
	int num = 1;//记录可以参加的活动数量
	for(int i = 1;i < n;i++){
		if(a[i].s >= last){//如果当前活动的开始时间大于等于last，那么活动可以参加，last更新 
			num++;
			last = a[i].e;
		}
	} 
	//输出num
	cout << num; 
	return 0;
} 

时间复杂度

$O(n)$(线性时间复杂度)

空间复杂度

$O(1)$(常数空间复杂度)