（Java实现） 整数区间

一、题目描述

给n个区间，形式为[a, b]，a和b均为整数，且a < b。

求一个最小的整数点的集合，使得每个区间至少2个不同的元素(整数点)属于这个集合。

求这个集合的元素个数。

输入

第1行：1个整数n(1 <= n <= 10000)

接下来n行，每行2个整数，表示区间的左右端点a, b(0 <=a < b <= 10000)

输出

第1行：1个整数，表示集合的元素的个数

样例输入

4

3 6

2 4

0 2

4 7

样例输出

4

二、定义解释

区间：就像线段一样，给出线段的端点坐标a、b（a<b），a和b之间的部分就叫区间。

开区间：(a,b)------区间中不包含a,b的值。

闭区间：[a,b]------区间中包含a,b的值。

整数闭区间中的元素：如：闭区间[3,6]中的元素有3、4、5、6.

集合：满足某条件的所有的数。

三、分析

这道题比较难懂，我看了很久才发现题目的意思，就是给你n个闭区间，找一些数使每一个闭区间都有这些数中的两个数。我们可以先把原数据存入结构体中，再重载运算符，方便排序。

import java.util.Scanner;public class zhengshuqujian {
//贪心算法-整数区间
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] a = new int[N];//下限
int[] b = new int[N];//上限
int[] n = new int[1000];
int output = 0;
for (int i = 0; i < N ; i++) {
a[i] = sc.nextInt();
b[i] = sc.nextInt();
}
//按上限的大小，从小到大排序。
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
if(b[j]<b[i]){
int temp = b[j];
b[j] = b[i];
b[i] = temp;
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
}
//从区间中取数，标记在n[]数组中。
for (int i = 0; i < N; i++) {
int flag = 0;//用于表示该区间内已经取了多少个数。
for (int j = a[i]; j < b[i]+1; j++) {
flag += n[j];
}
if(flag==0){
n[b[i]-1]=1;
n[b[i]]=1;
}
else if(flag == 1){
n[b[i]]=1;
}
else{
break;
}
//switch (flag) {
//case 0:
//n[b[i]-1] = 1;
//n[b[i]] = 1;
//break;
//case 1:
//n[b[i]] = 1;
//break;
//default:
//break;
//}
}
for (int i = 0; i < n.length; i++) {
output += n[i];
}
System.out.println(output);
}}