java题解 1555: 蓝桥杯算法提高VIP-线段和点（邻接表+贪心+排序+尺取法）

解题思路:

本题采用了邻接表+贪心+排序+尺取法的方法解题。

首先用邻接表存储给出的线段。

排序用在：

        1.遍历邻接表时，与遍历到的点所连接的点采用升序排序，这样取第0个元素，即为最小的点

        2.对读入的点按照升序排序。

贪心用在遍历到点i时，每次遍历时选择长度最短的，那么它可以满足以点i为起点，最多的线段

尺取法，定义尺子[start, end]， start为选取到的点的最大值，end为此时可满足的最近端点：

        与一般尺取法不同的的是，我设计的尺子的起点(start)为选择到的点中最大的点。由于定义读入的点序列是升序的，所以start只能前移、不能后退，而end则是可以双向移动的。对于本题来说，end值意义不大，主要是用来判断是否出现了找不到的情况。

        在循环中，首先判断遍历到的端点i是否小于start，如果小于start，

                    在有解的情况下，目前选取到的点足够满足端点i的所有情况

                    假定端点i的一个区间[i, k]，尺子区间为[start, end]，只要证明k大于等于start即可：

                           如果start>k，由于start为递增点序列中选取到的某点，如果start>k，那么后续所有的点均大于k，则不可能满足[i, k]这个区间，则无解。

                    所以在有解的情况下，一定有start包含在[i, k]这个区间这个真命题。

        不断更新start和end，遇到start<i的情况，则更新start，并根据实际的点序列确定是否要增加选取到的点序列的长度。

        如果在循环中出现了start>end的情况，那么证明出现了上述假设的情况，输出-1即可。

注意事项:详情可见我的注释。

参考代码:

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

// https://www.dotcpp.com/oj/problem1555.html
// （邻接表+贪心+排序+尺取法）
public class Main {
    static StreamTokenizer cin;
    static PrintWriter out;
    static int n;
    static int m;
    static Set  points;
    static ArrayList[] edges;
    public static void main(String[] args) throws IOException{
        cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
        n = nextInt();
        m = nextInt();
        points = new TreeSet<>();
        edges = new ArrayList[50001];
        for(int i = 0; i < 50001; i++){
            edges[i] = new ArrayList<>();
        }
        for(int i = 0; i < n; i++){
            points.add(nextInt());
        }
        for(int i = 0; i < m; i++){
            int a = nextInt();
            int b = nextInt();
            edges[a].add(b);
        }
        int end = Integer.MAX_VALUE;  // 此时可满足的最近端点
        int count = 0; // 所需点的个数
        int start = 0; // 起始点
        boolean flag = false;
        // start为选取到的点的最大值
        Iterator iterator = points.iterator();
        for(int i = 0; i < 50001; i++){  // 遍历邻接表
            if(start > end){  // 此时无解, 具体分析见下
                flag = true;
                break;
            }
            int len = edges[i].size();
            if(len != 0){
                Collections.sort(edges[i]);  // 排序
                int min = edges[i].get(0);  // 选取该点对应线段最小值
                if(start >= i){
                    // 此时不需要更新选择到的点, 因为start为选取到的所有点中的最大值:
                        // 当start大于i时,
                            // 如果有解, 一定会存在[i, min]包含start,
                                // 因为点是升序排序的, 如果现在的最大点都没包含在这个区间内, 那么后续的点更大, 更不可能包含在此区间内
                            // 如果没解, 则会出现end > start的情况, 此时退出循环, 输出-1
                    if(min < end) // 只需要更新上限, 不需选取下一个点
                        end = min;
                    continue;
                }
                while(iterator.hasNext()){
                    int t = iterator.next();
                    // 进入循环只能是因为下限不够, 即start=i && t  end  || end > Integer.MAX_VALUE/2){
                            // 加入新点, 同时更新区间
                            count++;
                            end = min;  // 更新区间
                        }
                        if(min < end)  // 只更新终点
                            end = min;
                        break;
                    }
                }
            }
        }
        if(flag)
            out.println(-1);
        else
            out.println(count);
        out.println();
        out.flush();
    }
    static int nextInt() throws IOException{
        cin.nextToken();
        return (int)cin.nval;
    }

}