C++ 解法, 执行用时: 60ms, 内存消耗: 2040KB, 提交时间: 2022-05-01

#include <bits/stdc++.h>

using namespace std;
int n;
#define maxn 200000+10
struct node
{
    int st,ed;
    bool operator < (const node & tmp)const 
    {
        return ed < tmp.ed;
    }
}a[maxn];
int main()
{
    scanf("%d",&n);
    int st,ed;
    for(int i =0;i<n;i++)
    {
        scanf("%d%d",&a[i].st,&a[i].ed);
    }
    sort(a,a+n);
    int cnt=0;
    int pre = -1;
    for(int i =0;i<n;i++)
    {
        if(a[i].st >= pre)
        {
            cnt++;
            pre = a[i].ed;
        }
    }
    printf("%d\n",cnt);
    return 0;
}

C++ 解法, 执行用时: 68ms, 内存消耗: 3460KB, 提交时间: 2022-04-13

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<stack>
#include<sstream>
#include<math.h>
#include<bitset>
#include<queue>
#include<iostream>
using namespace std;
int n,ans=0;
struct node {
	int a;
	int b;
}h[200005];
struct nodd{
	int aa;
	int bb;
}k[200005];
bool cmp(node x,node y){
	return x.b<y.b;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d%d",&h[i].a,&h[i].b);
	sort(h+1,h+1+n,cmp); 
	int m=0;
	for(int i=1;i<=n;i++){
		if(i==1) {
			k[m].aa=h[i].a;
			k[m].bb=h[i].b;
			m++;
			ans++;
			continue;
		}
		if(h[i].a>=k[m-1].bb) {
			ans++;
			k[m].aa=h[i].a;
			k[m].bb=h[i].b;
			m++;
        }
	}
	cout<<ans<<endl;
	return 0;
}

C 解法, 执行用时: 69ms, 内存消耗: 1784KB, 提交时间: 2022-06-07

#include <stdio.h>
#include <stdlib.h>
 
//快速排序法
int quick_sort(int *a, int *b, int low, int high)
{
    int i = low; //第一位
    int j = high; //最后一位
    
    int temp = rand()%(high-low)+low;
    int keya = a[temp]; //将第一个数作为基准值-- 先找到一个基准值
    int keyb = b[temp];
    a[temp]=a[i];
    b[temp]=b[i];
    
    //进行排序---> 最终结果就是 左面的 都比基准值小 ，右面的都比 基准值大，所以这是所有循环的结束条件

    while (i < j)
    {
        //下面的循环执行的条件是 如果右面的比基准值大，就赋一下值，否则继续向前移动
        //---如果直接把循环写成下面这样---
        //while(a[j] >= key) //如果下面的不写这个i<j,这个就出错、越界，并且排序不准--理由：
        //如果i<j,并且： 右面的值 大于 基准值 时，j往前移动一个
        //i 跟 j 的可能情况 只有 i<j i==j
        while(i < j && b[j] >= keyb)//i<j 是 当前while循环的结束条件，如果没有这个，i会大于j，出现越界，错误 
        {
            j--;//继续走
        }//如果不成立，也就是 a[j] <= key;右面的比key小了，那就换个位置
        //把a[j]的数据给a[i]	
        b[i] = b[j];
        a[i] = a[j];
 
        //将事先保存好的基准值与左边的值进行比较，如果基准值大，保持不变，i往前
        //然后 判断一下这个新的a[i]，也就是之前的a[j]跟key值的关系---> 一定是 a[i]<key
        //所以把i向前移动一下，i++
        while(i < j && b[i] < keyb)
        {
            i++;
        }
        //移动完以后，把新的位置的a[i]的数值 给刚才的 a[j],然后开始下一次循环
        b[j] = b[i];
        a[j] = a[i];
    }
 
    //跳出循环，将基准值放入数据a[i]中
    b[i] = keyb;
    a[i] = keya;
    //对基准值左边 的所有数据 再次进行快速查找（递归）
    if (i-1 > low) 
    {
        quick_sort(a, b, low, i-1);
    }
 
    //对基准值右边的所有数据再次进行快速查找（递归）
    if (i+1 < high)
    {
        quick_sort(a, b, i+1, high);
    }
 
    return 0;
} 
 
int main()
{
    int num;
    scanf("%d", &num);

    int raws[num];
    int rawf[num];
    
    for (int i=0;i<num;i++){
        scanf("%d %d", &raws[i], &rawf[i]);
    }
 
    //调用-快排
    quick_sort(raws, rawf, 0, num-1);//数组，0 ，num-1

 
    // 选择数据
    int curend=rawf[0];
    int count=1;
    
    for (int k=1;k<num;k++){
        if(raws[k]>=curend){
            curend=rawf[k];
            count++;
        }
    }

    printf("%d",count);   
    
    
    return 0;
}




/*int main(){
    int num;
    scanf("%d", &num);

    int raws[num];
    int rawf[num];
    int rawdiff[num];
    
    for (int i=0;i<num;i++){
        scanf("%d %d", &raws[i], &rawf[i]);
        //rawdiff[i]=rawf[i]-raws[i];
    }

    int sorts[num];
    int sortf[num];
    int sortdiff[num];
    int sortcount=0;

    // 双重排序
    for (int j=0; j<num; j++){
    if(j==0){
        sorts[0]=raws[0];
        sortf[0]=rawf[0];
        //sortdiff[0]=rawdiff[0];
        //sortcount++;
                 }
    else{
        for(int m=0;m<num;m++){
            if(rawf[j]<=sortf[m]){
                    for(int n=j;n>m;n--){
                       sorts[n]=sorts[n-1];
                       sortf[n]=sortf[n-1];
                       //sortdiff[m]=sortdiff[n-1];
                    }
                    sorts[m]=raws[j];
                    sortf[m]=rawf[j];
                    //sortdiff[m]=rawdiff[j];
                    //sortcount++;
                    break;
            }
            else{
                if((m+1)<j)
//                    if(raws[j]>=sorts[m] && raws[j]<sortf[m]){
//                        break;
//                    }
//                    else 
                    continue;
                else{
                    sorts[j]=raws[j];
                    sortf[j]=rawf[j];
                    //sortdiff[j]=rawdiff[j];
                    //sortcount++;
                }
            }
         }
      }
    }

    // 选择数据
    int index=0;
    int count=1;

    for (int k=1;k<num;k++){
        if(sorts[k]>=sortf[index]){
            index=k;
            count++;
        }
    }

printf("%d",count);


}*/

C 解法, 执行用时: 71ms, 内存消耗: 1804KB, 提交时间: 2022-06-19

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

void quickSort(int *a, int *b, int start, int end) {
    if (start < end) {
        int tempIndex = rand()%(end - start + 1)+start, tmp;
        tmp = b[start];
        b[start] = b[tempIndex];
        b[tempIndex] = tmp;
        tmp = a[start];
        a[start] = a[tempIndex];
        a[tempIndex] = tmp;
        
        int target = b[start], targetA = a[start], i = start, j = end;
        while(i < j) {
            while(i < j && b[j] > target) {
                j--;
            }
            if(i < j) {
                b[i] = b[j];
                a[i] = a[j];
                i++;
            }
            while(i < j && b[i] < target) {
                i++;
            }
            if(i < j) {
                b[j] = b[i];
                a[j] = a[i];
                j--;
            }
        }
        b[i] = target;
        a[i] = targetA;
        
        quickSort(a, b, start, i - 1);
        quickSort(a, b, i + 1, end);
    }
}

int cmp(const void **a, const void **b) {
    return (*((int **)a))[1] - (*((int **)b))[1];
}

int main() {
    int n, i = 0, count = 0;
    scanf("%d", &n);
    
    int *a = (int *)malloc(sizeof(int) * n);
    int *b = (int *)malloc(sizeof(int) * n);
    while(i < n) {
        scanf("%d %d", &a[i], &b[i]);
        
        i++;
    }
    
    quickSort(a, b, 0, n - 1);
      
    i = 0;
    count = 0;
    int minEnd = b[0], nextEnd, startK = 0;
    while(minEnd != 1000000001) {
        count++;
        
        nextEnd = 1000000001;
        for (int k = startK; k < n; k++) {
            if (a[k] >= minEnd && b[k] < nextEnd) {
                nextEnd = b[k];
                startK = k + 1;
                break;
            }
        }
        
        minEnd = nextEnd;
    }
    free(a);
    free(b);
    
//     int **ab = (int **)malloc(sizeof(int *) * n);
//     while(i < n) {
//         ab[i] = (int *)malloc(sizeof(int) * 2);
        
//         scanf("%d %d", &ab[i][0], &ab[i][1]);
        
//         i++;
//     }

//     qsort(ab, n, sizeof(int *), cmp);
    
//     i = 0;
//     count = 0;
//     int minEnd = ab[0][1], nextEnd, startK = 0;
//     while(minEnd != 1000000001) {
//         count++;
        
//         nextEnd = 1000000001;
//         for (int k = startK; k < n; k++) {
//             if (ab[k][0] >= minEnd && ab[k][1] < nextEnd) {
//                 nextEnd = ab[k][1];
//                 startK = k + 1;
//                 break;
//             }
//         }
        
//         minEnd = nextEnd;
//     }
//     for(i = 0; i < n; i++) {
//         free(ab[i]);
//     }
//     free(ab);
    
    printf("%d", count);
    
    return 0;
}

C++ 解法, 执行用时: 76ms, 内存消耗: 3576KB, 提交时间: 2022-04-01

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
int n, ans;
struct node{
	int a;
	int b;
}h[maxn];
struct nodd{
	int aa;
	int bb;
}k[maxn];
bool cmp(node &x,node &y){
	return x.b < y.b;
}
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) 
        cin >> h[i].a >> h[i].b;
	sort(h + 1, h + 1 + n, cmp); 
	int m = 0;
	for(int i = 1; i <= n; i++){
		if(i == 1){
			k[m].aa = h[i].a;
			k[m].bb = h[i].b;
			m++;
			ans++;
		}
		else if(h[i].a >= k[m-1].bb){
			ans++;
			k[m].aa = h[i].a;
			k[m].bb = h[i].b;
			m++;
        }
	}
	cout << ans << endl;
	return 0;
}