区间选点

这是一道贪心题，之前我对贪心的认识很浅显，就认为是给了题目直接贪心，像这道题目还需要先排序

二维数组快速排序方法!!!

真的很重要

一开始我用的是冒泡排序法，代码较长而且时间复杂度较高，在网上查询了一些算法之后，发现使用sort 构造cmp函数，然后将数组转化为结构体使用比较方便且快捷
接下来写几个练练手

sort排序

1.用cmp控制一维数组升序和降序

#include<iostream>
#include<algorithm>

using namespace std;

bool cmp(int x,int y){
	return x>y;//这里可以把x看成前一个，y看作后一个，因此x>y时就是降序 
}

const int N=100;
int a[N];

int main(){
	
	int n;
	
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
		
	cout<<"排序前"<<endl;
	
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
		cout<<endl;
	
	//正常的默认升序排序 sort(a+1,a+1+n);
	sort(a+1,a+1+n,cmp);//利用cmp可以升序以及降序 
	
	cout<<"排序后"<<endl;
	
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
		cout<<endl;
	
	return 0;
} 

2. 对结构体（二维数组）排序

#include<iostream>
#include<algorithm>

using namespace std;


const int N=100;

struct node{
	int a,b;//定义节点，成员相当于二维数组的两个维度 
};

node q[N];//结构体数组，看作二维数组 

bool cmp(node x,node y){//注意这里要写node,作为元素类型 
	return x.b>y.b;//这里可以把x看成前一个，y看作后一个，因此x>y时就是降序 
					//.b就是比较第二个元素 
}

int main(){
	
	int n;
	
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>q[i].a>>q[i].b; 
		
	cout<<"排序前"<<endl;
	
	for(int i=1;i<=n;i++)
		cout<<q[i].a<<" "<<q[i].b<<endl;
	
	//正常的默认升序排序 sort(a+1,a+1+n);
	sort(q+1,q+1+n,cmp);//利用cmp可以升序以及降序 
	
	cout<<"排序后"<<endl;
	
	for(int i=1;i<=n;i++)
		cout<<q[i].a<<" "<<q[i].b<<endl;
	
	return 0;
} 

因为直接对二维数组的排序我也没怎么看懂，因此就利用结构体，结果都一样

算法题代码

/*
给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

输入格式
第一行包含整数 N，表示区间数。

接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。

输出格式
输出一个整数，表示所需的点的最小数量。

数据范围
1≤N≤10^5,
-10^9≤ai≤bi≤10^9
输入样例：
3
-1 1
2 4
3 5
输出样例：
2
*/

/*
思路：
	尽管给出的区间顺序可能不是按照端点大小排列的，但是当你在纸上画出来的时候会发现区间是有些顺序的
	而且每次尽量取某个区间的最右边的点能够使得它可能会覆盖更多的点。
	因此思路为：
		将所给区间按照右端点排序，从第一个开始，取最右边的点，如果该点可以覆盖下一个区间，那么就继续找下一个区间
		直到该点无法覆盖当前区间，取当前区间的右端点再作为一个点，以此类推，直到最后一个区间 
*/ 

#include<iostream>
#include<algorithm>

using namespace std;

const int N=110000;
int n;
int a[N][2];

struct node{
	int a,b;
};

node q[N];

bool cmp(node x,node y){
	return x.b<y.b;
}


int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	 	cin>>q[i].a>>q[i].b;//存入左右端点
		 
	/*	 
	for(int j=0;j<n-1;j++){
		for(int i=1;i<=n-j-1;i++){
			if(a[i][1]>a[i+1][1]){
				int t=a[i][1];
				a[i][1]=a[i+1][1];
				a[i+1][1]=t;
				
				t=a[i][0];
				a[i][0]=a[i+1][0];
				a[i+1][0]=t;	
			}
		}
	}	 //将区间按照右端点排序 
	*/
	
	sort(q+1,q+1+n,cmp);
	
	int ans=1;
	
	
	for(int i=1;i<=n;i++){
		a[i][0]=q[i].a;
		a[i][1]=q[i].b;
	}
	//之前用的是a，于是就赋值了，后面没有修改成q 
	
	int p=a[1][1];//选取第一个区间最右侧的点 
	for(int i=1;i<=n;){
		while(p>=a[i][0]&&p<=a[i][1]){//当这个点在区间内 
			i++;
		} 
		//如果不在
		if(i>n)
			break;
		p=a[i][1];
		i++;
		ans++;
	}
	
	cout<<ans;
	
	return 0;
}