（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);

	}

}

巴特西

（Java实现）整数区间

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

最新文章

热门文章

巴特西

（Java实现） 整数区间

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

最新文章

热门文章

（Java实现）整数区间