I - Integer Intervals POJ - 1716

92 阅读 0 评论 61 点赞

我是靠谱客的博主高贵奇迹，最近开发中收集的这篇文章主要介绍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

Sample Output


//题目大意：给定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;
		}
	}
}