本题考查点结构体排序以及贪心，不能使用冒泡排序，会超时。

题意简介：给你n个活动的起始时间和截至时间，任意两个活动的时间不能交叉，问你最优的安排可以完成几个活动。

解法：对各个活动的结束时间进行从小到大排序（画图理解一下）。然后判断后面的活动的起始时间是否大于上一个活动的结束时间， 满足的话说明这个活动可以完整举行。

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
struct ch
{
	int st, ed;
}s[N];
bool cmp (ch a, ch b)
{
	return a.ed < b.ed;
}
int main()
{
	int t;
	scanf("%d", &t);
	while (t --)
	{
		int n;
		scanf("%d", &n);
		for (int i = 1;i <= n;i ++)
		{
			scanf ("%d %d",&s[i].st, &s[i].ed); 
		}
		
		sort(s + 1,s + 1 + n, cmp);
		int ans = 1;
		int last = s[1].ed;
		for (int i = 2; i <= n;i ++)
		{	
			if (last < s[i].st)
			{
				ans ++;
				last = s[i].ed;
			}
		}
		printf("%d\n",ans);
	}
}

#include<bits/stdc++.h>
using namespace std;
struct huodong
{
	int bi;//开始时间
	int ei;//结束时间
};
bool paixu (huodong b, huodong e)//布尔类型
{
	return b.ei < e.ei;
}
int main()
{
	int t,sum;
	cin>>t;
	while(t--)
	{ 
		sum = 1;
		int n;
		cin>>n;
		huodong hd[n];
		for(int i=0;i<n;i++)//对活动开始停止时间进行赋值
		{
			cin>>hd[i].bi;
			cin>>hd[i].ei;
		}
		sort(hd,hd+n,paixu);
		int temp = hd[0].ei;
		for(int i=1;i<n;i++)
		{
			if(temp<hd[i].bi)
			{
				sum++;
				temp = hd[i].ei;
			}
		}
		cout<<sum<<endl;
	}
}

//练习的结构体和sort排序
#include <algorithm>
#include <iostream>
using namespace std;

struct huiChangtimes {
  int start;
  int end;
};
bool zhengXu(huiChangtimes a, huiChangtimes b) { return a.end < b.end; }
int main() {
  int m = 0;
  cin >> m;
  for (int i = 0; i < m; i++) {
    int n = 0;
    cin >> n;
    huiChangtimes tim[n];
    for (int j = 0; j < n; j++) {
      cin >> tim[j].start >> tim[j].end;
    }
    sort(tim, tim + n, zhengXu);
    int times = 1;
    int lasttimes = tim[0].end;
    for (int j = 1; j < n; j++) {
      if (lasttimes < tim[j].start) {
        times++;
        lasttimes = tim[j].end;
      }
    }
    cout << times << endl;
  }
}

$\ \ \ \ \ \ \$python大法好，拒绝手写结构体排序，从我做起（实际上是py自带的关键字排序）。

m = int(input())
for _ in range(m):
    n = int(input())
    act = []
    act_num = 1
    for __ in range(n):
        lst = list(map(int, input().split( )))
        act.append(lst)
    act.sort(key = lambda x : x[1])
    pointer = 0
    for i in range(1, n):
        if act[i][0] > act[pointer][1]:
            act_num += 1
            pointer = i
    print(act_num)

还是用c语言，只不过借用c++的一个排序函数提交的时候把c改为c++提交。

#include <stdio.h>

#include <algorithm>

using namespace std;

typedef struct S{

int a;

int b;

}s;

bool ak47(s x,s y){

return x.b<y.b;

}

int main()

{

int t;

scanf("%d",&t);

while(t--){

int n;

scanf("%d",&n);

s ar[n];

for(int i=0;i<n;i++){

scanf("%d %d",&ar[i].a,&ar[i].b);

} sort(ar,ar+n,ak47);

int sum=1;

int al=ar[0].b;

for(int i=1;i<n;i++){

if(al<ar[i].a){

sum++;

al=ar[i].b;

}

} printf("%d\n",sum);

}

return 0;

}

确实巧妙。 不想创建结构体的同学也可以选择c++的piar类来替代此处的自定义结构体。 不知道为什么，没办法上传代码块，上传代码块会更新错误。 下为代码： #include<iostream> #include<vector> #include<utility> #include<algorithm> using namespace std; template<class T> class Less { public: bool operator()(const T& a , const T& b) { return a.second < b.second; } }; int main() { int m; cin >> m; while(m--) { int n; cin >> n; vector<pair<int , int>> _v(n); for(int i = 0 ; i < n ; i++) { cin >> _v[i].first >> _v[i].second; } sort(_v.begin() , _v.end() , Less<pair<int , int>>()); int ret = 1; int comp = _v[0].second; for(int i = 1 ; i < n ; i++) { if(comp < _v[i].first) { ret++; comp = _v[i].second; } } cout << ret << endl; } return 0; }

参考VAC，给出rust实现。

use std::io::{self, BufRead};

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines().map(|line| line.unwrap());
    let m: i32 = lines.next().unwrap().parse().unwrap();

    for _ in 0..m {
        let n: usize = lines.next().unwrap().parse().unwrap();
        let mut activities = Vec::new();

        // 读取每个活动的起始时间和结束时间
        for _ in 0..n {
            let line = lines.next().unwrap();
            let split: Vec<i32> = line
                .split_whitespace()
                .map(|x| x.parse().unwrap())
                .collect();
            activities.push(split);
        }

        // 按照结束时间升序排序
        activities.sort_by(|a, b| a[1].cmp(&b[1]));

        let mut act_num = 1; // 已安排的活动数量
        let mut pointer = 0; // 指向上一个活动的索引

        // 从第二个活动开始，检查是否与前一个活动时间冲突
        for i in 1..n {
            if activities[i][0] > activities[pointer][1] {
                // 没有时间冲突，可以安排该活动
                act_num += 1;
                pointer = i;
            }
        }

        println!("{}", act_num); // 输出结果
    }
}