[数据结构与算法]112. 雷达设备 Java题解 （贪心）

输入样例：

3 2
1 2
-3 1
2 1

输出样例：

2

解题思路：

题目让求至少有多少雷达可以将所有岛都覆盖，如过计算雷达的覆盖范围的话，非常麻烦，因为雷达的范围是一个二维的圆。但是可以转化为对于每个岛，计算雷达在坐标轴的哪个区间安放可以被完全覆盖该岛屿。

所以问题就转化成了在坐标轴上的一些区间，选择尽量少的点，使得每个区间至少包含一个点（不是很严格的可以看成求一些区间的交集个数，如果将单个点也视为区间）。

步骤：将所有区间按有段点排序，取第一个区间右端点为r；当端点r可以被下个区间完全包括时，跳过；当右端点r不能被下个区间包括时（即下个区间的左端点大于r），取该区间的有段点更新为r作为新的雷达。

Java代码：（按右端点排序）

import java.io.*;
import java.util.Arrays;

public class Main {
	static class Point implements Comparable<Point>{
		double l, r;
		public Point(double l, double r) {
			this.l = l;
			this.r = r;
		}
		@Override
		public int compareTo(Point o) {  //  按右端点排序
			if(this.r != o.r) return Double.compare(this.r, o.r);
			else return Double.compare(this.l, o.l);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int n = Integer.parseInt(split[0]);
		int d = Integer.parseInt(split[1]);
		Point []p = new Point[n];
		
		boolean flag = false;
		for(int i = 0; i < n; i++) {
			split = br.readLine().split(" ");
			int x = Integer.parseInt(split[0]);
			int y = Math.abs(Integer.parseInt(split[1]));
			if(y > d) flag = true;
			
			double x1 = x + Math.sqrt(d * d - y * y);
			double x2 = x - Math.sqrt(d * d - y * y);
			
			p[i] = new Point(x2, x1);
		}
		
		if(flag) System.out.println("-1");
		else {
			Arrays.sort(p);
			
			int ans = 1;
			double r = p[0].r;
			for(int i = 1; i < n; i++) {
				if(p[i].l > r) {
					ans++;
					r = p[i].r;
				}
			}
			System.out.println(ans);
		}
	}
}

Java代码：（按左端点排序）

import java.io.*;
import java.util.Arrays;

public class Main {
	static class Point implements Comparable<Point>{
		double l, r;
		public Point(double l, double r) {
			this.l = l;
			this.r = r;
		}
		@Override
		public int compareTo(Point o) {
			if(this.l != o.l) return Double.compare(this.l, o.l);
			else return (int)(this.r * 1000 - o.r * 1000);
		}
	}
	
	@SuppressWarnings("unused")
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int n = Integer.parseInt(split[0]);
		int d = Integer.parseInt(split[1]);
		Point []p = new Point[n];
		
		boolean flag = false;
		for(int i = 0; i < n; i++) {
			split = br.readLine().split(" ");
			int x = Integer.parseInt(split[0]);
			int y = Math.abs(Integer.parseInt(split[1]));
			if(y > d) flag = true;
			
			double x1 = x + Math.sqrt(d * d - y * y);
			double x2 = x - Math.sqrt(d * d - y * y);
			
			p[i] = new Point(x2, x1);
		}
		
		if(flag) System.out.println("-1");
		else {
			Arrays.sort(p);
			
			int ans = 1;
			double l = p[0].l;
			double r = p[0].r;
			for(int i = 1; i < n; i++) {
				if(p[i].l <= r) {
					if(p[i].r < r) r = p[i].r;
					else l = p[i].l;
				}else if(p[i].l > r){ 
					ans++;
					l = p[i].l;
					r = p[i].r;
				}
			}
			System.out.println(ans);
		}
	}
}