算法分析

区间选点问题，将每个坐标映射成x轴上的区间，表示在这个区间上装雷达，就能探测到这个小岛,在给定的区间，选最少的点，使得每个区间内至少包含一个选出的点。

• 1、将每个区间按右端点从小到大进行排序

• 2、从前往后枚举每个区间，初始选定end值为无穷小

  • 若当前区间中包含该点end，则直接跳过
  • 否则，选择当前区间的右端点

• 证明：

  • (1)找到cnt个点，满足题意情况，则最优解Ans <= cnt
  • (2)找到cnt个点，即找到cnt个区间，且区间从左到右依次排好，且没有相同的交集，则说明可能有区间没有被这cnt个点覆盖过，所以最优解Ans >= cnt
  • 则Ans == cnt，证毕

时间复杂度 $O(nlogn)$

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 1010;
    static Pair[] pair = new Pair[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int d = scan.nextInt();
        boolean flag = true;
        for(int i = 0;i < n;i ++)
        {
            int x = scan.nextInt();
            int y = scan.nextInt();
            if(d < y) flag = false;
            else
            {
                double len = Math.sqrt(d * d - y * y);
                double l = x - len;
                double r = x + len;
                pair[i] = new Pair(l,r);
            }
        }
        if(!flag) System.out.println("-1");
        else
        {
            Arrays.sort(pair,0,n);
            double end = pair[0].r;
            int res = 1;
            for(int i = 1;i < n;i ++)
            {
                if(pair[i].l <= end) continue;
                end = pair[i].r;
                res ++;
            }
            System.out.println(res);
        }
    }
}
class Pair implements Comparable<Pair>
{
    double l,r;
    Pair(double l,double r)
    {
        this.l = l;
        this.r = r;
    }
    @Override
    public int compareTo(Pair o) {
        // TODO 自动生成的方法存根
        return Double.compare(r, o.r);
    }
}