问题标题: 酷町堂：2777 区间合并

题目描述 Description

区间是指具有左端点和右段点的，在左端点和右端点间所有数的集合。例如(2, 6)就是指2到6之间的所有数。现在给你n个区间，请你将它们合并成尽可能少的区间。区间合并的规则是，如果两个区间有公共部分，或者端点相连，则可以变成一个更大的区间。

输入描述 Input Description

第一行，一个整数，n，表示有n个区间
接下来n行，每行两个整数，a b，表示区间(a, b)

输出描述 Output Description

一个整数，表示合并之后还剩多少个区间

样例输入 Sample Input

4 1 5 2 4 1 4 2 3

样例输出 Sample Output

1

数据范围及提示 Data Size & Hint

n≤100

 

0分

#include<bits/stdc++.h>
using namespace std; 
int n,cnt;
struct sj{
	int st,ed;
}a[105]; 
bool cmp(sj x,sj y){
	return x.ed<y.ed;
}
int main(){ 
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].st>>a[i].ed;
	}
	sort(a+1,a+1+n,cmp);
	int end=-1;
	for(int i=1;i<=n;i++){
		if(a[i].st>=end){
			cnt++;
			end=a[i].ed;
		}
	} 
	cout<<cnt;
	return 0; 
}

 

陈正朔在2021-03-29 19:28:46追加了内容

d

陈正朔在2021-03-31 18:58:51追加了内容

1