，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);
        }


}