挑选代表

[编程题]挑选代表

热度指数：3981 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

我们有很多区域，每个区域都是从a到b的闭区间，现在我们要从每个区间中挑选至少2个数，那么最少挑选多少个？

输入描述:

第一行是N（N<10000）,表示有N个区间，之间可以重复
然后每一行是ai,bi，持续N行，表示现在区间。均小于100000

输出描述:

输出一个数，代表最少选取数量。

示例1

输入

输出

算法知识视频讲解

Java

JLU小浪

import java.util.Arrays;
import java.util.Scanner;
//52
/*右端点排序,按条件判断(倾向于选最右边的)*/
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] a = new int[n][2];
		for (int i = 0; i < n; i++) {
			a[i][0] = sc.nextInt();
			a[i][1] = sc.nextInt();
		}
		Arrays.sort(a, (a1, a2) -> a1[1] - a2[1]); // 右端点排序
		int res = 2;// 至少需要两个
		int temp = a[0][1];
		for (int i = 1; i < n; i++) {
			if (a[i][0] > temp) {
				res += 2;
				temp = a[i][1];
			} else if (a[i][0] == temp) {
				res += 1;
				temp = a[i][1];
			}
		}
		System.out.println(res);

	}
}

编辑于 2019-09-15 18:18:06 回复(1)