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

题意简介：给你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的写法，使用了qsort进行排序,也因此需要写出相应的比较函数

#include <stdio.h>
#include <stdlib.h>

typedef struct Activity{
    int start;
    int end;
} Activity;

Activity activity[10000];


int n;
int ans;

void init() {
    int s,e;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &s, &e);
        activity[i].start = s;
        activity[i].end = e;
    }
}

int cmp(const void *a, const void *b) {
    Activity *x = (Activity *)a;
    Activity *y = (Activity *)b;
    if (x->end == y->end) {
        return x->start - y->start;
    } else {
        return x->end - y->end;
    }
}

void solve() {
    qsort(activity, n, sizeof(Activity), cmp);

    ans = 1;
    int last = activity[0].end;

    for (int i = 1; i < n; i++) {
        if (activity[i].start >= last + 1) {
            ans++;
            last = activity[i].end;
        }
    }
    printf("%d\n", ans);
}


int main() {
    int m;
    scanf("%d", &m);

    for (int i = 0; i < m; i++) {
        init();
        solve();
    }

    return 0;
}

以下为qsort函数原型

void qsort(
    void *base,        // 待排序数组的首地址（任意类型指针）
    size_t nmemb,      // 数组中元素的个数
    size_t size,       // 每个元素的大小（单位：字节）
    int (*compar)(const void *, const void *)  // 比较函数指针
);

还是用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;

}

参考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); // 输出结果
    }
}

#include <stdio.h>
#include <algorithm>
using namespace std;
struct act{
    int start;
    int end;
};
bool cmp(act a1,act a2){
    return a1.end<a2.end;
}
int main(){
    int m;
    scanf("%d",&m);
    while(m--){
        int n,i=0,cnt=0;
        act a[10001];
        scanf("%d",&n);
        while(i<n){
            scanf("%d%d",&a[i].start,&a[i].end);
            i++;
        }
        sort(a,a+n,cmp);
        int end=-1;
        for(i=0;i<n;i++){
            if(a[i].start>end){
                cnt++;
                end=a[i].end;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;
struct Activity {
    int start;
    int end;
};
bool cmp(Activity a, Activity b) {
    return a.end < b.end;//结束时间小的在左边的意思
}
int main()
{
    int m,n;
    scanf("%d",&m);
    while(m--)//m组
    {
        scanf("%d",&n);//n个活动
        Activity activities[10001];  // 使用结构体数组
        // 读取所有活动
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&activities[i].start, &activities[i].end);
        }
        // 按结束时间排序
        sort(activities, activities + n, cmp);
        int count = 0;
        int lasttime = -1;
        for(int i=0;i<n;i++)
        {
            if(lasttime < activities[i].start)
            {
                count++;
                lasttime = activities[i].end;
            }
        }
        printf("%d\n",count);
    }
    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; }