小贪心

用户名：uq_90082943905

访问量：2210

签　名：

等　　级
排　　名	4427
经　　验	1490
参赛次数	0
文章发表	7
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1324-整数区间-题解(Java代码)
浏览：386

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

优质题解

信息学奥赛一本通T1324-整数区间-题解(Java代码)

　　作者: 小贪心　　　　发表时间：2020-02-27 11:55:57 浏览：386　|　评论：0　

原题链接：信息学奥赛一本通T1324-整数区间

## 整数区间

时间限制: 1Sec 内存限制: 128MB

**题目描述**
请编程完成以下任务：

1.从文件中读取闭区间的个数及它们的描述；

2.找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合，输出该集合的元素个数。

**输入**
首行包括区间的数目n,1≤n≤10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0≤a≤b≤10000,它们是某一个区间的开始值和结束值。
**输出**
第一行集合元素的个数,对于每一个区间都至少有一个整数属于该区间,且集合所包含元素数目最少。
**样例输入**
4
3 6
2 4
0 2
4 7
**样例输出**
2

## 思路
模型为**给n个闭区间，在数轴上选尽量少的点，使每个区间内至少有一个点**

首先**多关键词排序**：数据按右区间升序排序。排序优先级：右区间>左区间，也就是当右区间相同时，升序比较左区间。
其次**循环标记**：每次标记区间右端点x，并右移当前区间指针，直到当前区间不包含x，再重复上述步骤。

```java
import java.util.Scanner;

public class Main {
	static int[] a=new int[10001];
	static int[] b=new int[10001];
	static int n=0;
	public static void main(String[] args){
		data();   //数据初始化
		qsort(0,n-1);  //多关键词排序
		solve();  //循环标记
	}
	static void data(){
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		
		for(int j=0;j<n;j++){
			a[j]=sc.nextInt();
			b[j]=sc.nextInt();
		}
	}
	
	static void qsort(int x,int y){
		int i=x , j=y ,mid1=b[(x+y)/2] , mid2=a[(x+y)/2], t=0;
		while(i<=j){
			while((b[i]<mid1)|| ((b[i]==mid1)&& (a[i]<mid2))) i++;  //比较条件
			while((b[j]>mid1)|| ((b[j]==mid1)&& (a[j]>mid2))) j--;  //比较条件
			if(i<=j){
				t=b[i]; b[i]=b[j]; b[j]=t;
				t=a[i]; a[i]=a[j]; a[j]=t;
				i++;j--;
			}
		}
		if(x<j) qsort(x,j);
		if(i<y) qsort(i,y);
			
	}
	static void solve(){
		int sum=0;
		for(int i=0,x=-1;i<n;i++){
			if(x>=a[i]) continue;   //如果当前区间包含标记点 则跳过
			sum++; 					
			x=b[i];					//更新标记点
		}
		System.out.print(sum);
	}
}

```

0.0分

1 人评分

想学习C语言网的全部课程吗（C/C++、算法、百练、Python等包括后续更新的课程）？还有刷题助手，数据比对和分析，加上各种赚钱私活的锻炼机会，尽在C语言网plus会员，点击开通快人一步！

小贪心

TA的其他文章

你可能喜欢

模拟计算器（Java代码）

第一

聪明的美食家（C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

信息学奥赛一本通T1324-整数区间-题解(Java代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

这可能是一个假的冒泡法

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

数组输出（C语言代码）--此题的题目描述有问题

字符串比较（C语言代码）答案错误？？？？

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-大、小写问题（C语言代码）

简单的for循环

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

小贪心

TA的其他文章

你可能喜欢

模拟计算器 （Java代码）

第一

聪明的美食家 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

信息学奥赛一本通T1324-整数区间-题解(Java代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

这可能是一个假的冒泡法

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

数组输出 （C语言代码）--此题的题目描述有问题

字符串比较 （C语言代码）答案错误？？？？

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-大、小写问题 （C语言代码）

简单的for循环

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

模拟计算器（Java代码）

聪明的美食家（C语言代码）

　　评论区

C语言考试练习题_一元二次方程（C语言代码）

数组输出（C语言代码）--此题的题目描述有问题

字符串比较（C语言代码）答案错误？？？？

C语言训练-大、小写问题（C语言代码）