我是靠谱客的博主 高贵奇迹,这篇文章主要介绍I - Integer Intervals POJ - 1716,现在分享给大家,希望可以做个参考。

题目:

An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b. 
Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.

Input
The first line of the input contains the number of intervals n, 1 <= n <= 10000. Each of the following n lines contains two integers a, b separated by a single space, 0 <= a < b <= 10000. They are the beginning and the end of an interval.
Output
Output the minimal number of elements in a set containing at least two different integers from each interval.
Sample Input
4
3 6
2 4
0 2
4 7
Sample Output
4


//题目大意:给定N个闭区间,每个区间都要至少有两个数被选中,问最少有多少个数被选中
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int n;
		List<Interval> list = new ArrayList<Interval>();
		Scanner sc = new Scanner(System.in);
		Main ii = new Main();
		Interval iv;
		while (sc.hasNextInt()) {
			n = sc.nextInt();
			for (int i = 0; i < n; i++) {
				iv = ii.new Interval();
				iv.b = sc.nextInt();
				iv.e = sc.nextInt();
				list.add(iv);
			}
			// 区间左从小到大排序
			Collections.sort(list);
			// 区间取值范围
			int s = list.get(list.size() - 1).b;// 左
			int t = s + 1;// 右
			int sum = 2;// 结果
			for (int i = n - 2; i >= 0; i--) {

				if (list.get(i).e >= t) {
					continue;
				} else if (list.get(i).e < s) {
					s = list.get(i).b;
					t = s + 1;
					sum += 2;
				} else {
					t = s;
					s = list.get(i).b;
					sum++;
				}
			}
			System.out.println(sum);
			list.clear();
		}
	}

	/**
	 * 定义区间类
	 */
	class Interval implements Comparable {
		public int b;// 区间左
		public int e;// 区间右
		// 区间左按从小到大排序

		@Override
		public int compareTo(Object o) {

			return this.b - ((Interval) o).b;
		}
	}
}


最后

以上就是高贵奇迹最近收集整理的关于I - Integer Intervals POJ - 1716的全部内容,更多相关I内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(43)

评论列表共有 0 条评论

立即
投稿
返回
顶部