最方便的公寓

最方便的寓所
一列street block，每个street block上都有POI （Point of Interests），比如学校，商店，诊所等等。也可能没有。

给定一个list of requirements, 比如[grocery，school]，找到距离所有requirement最近的apartment位置。

follow up是如果只有一些street block有apartment怎么办

https://www.1point3acres.com/bbs ... read&tid=504803

确认一下＂最远的定义＂是一个点到所有最近requirement的点的总和？一个点到所有requirement中最远的距离？
sum((distance to r) for r in requirements)
or
max((distance to r) for r in requirements)
我看另一个面经的例子好像是后者

神秘文件的例子，原帖找不到了：
假设一条街上有多个block，一个block上有多个建筑。求一条街上离几个最近的特定建筑的最远距离最短的block。例子： street = [[“store”, “school”, “museum”], [“hospital”, “restaurant”], [“school”, “restaurant”], [], [“museum”]], requirement = [“store”, “museum”, “restaurant”].
第一个block到最近store是0，到最近museum是0，到最近restaurant是1，所以它的max是1
第二个block到最近store是1，到最近museum是1，到最近restaurant是0，所以它的max是1
第三个block到最近store是2，到最近museum是2，到最近restaurant是0，所以它的max是2
第四个block到最近store是3，到最近museum是1，到最近restaurant是1，所以它的max是3
第五个block到最近store是4，到最近museum是0，到最近restaurant是2，所以它的max是4
所以返回的block是第一个和第二个。


题意有误解，这题有两种问法，一种是问距离和，一种是问到最远的一个的距离，距离和的话这个作法当然是不对的，如果只是到最远的requirement 的距离，500距离0和1000都是500，这例子就没问题

粘一个个人的答案，无论是求距离和还是最远都可以用这个方法，速度为O（nk），k为requires项数。

    * Input: 1. 给一条路，路上的不同位置有不同的设施，有多个设施在不同位置的情况, List<Set<String>>

    *        2. 给一个需求设施的set

    * Output： 希望给出一个位置，距离所有设施的距离最近的和

    *

    * Example:

    *   Road: {

    *           [bookstore, school],

    *           [grocery] ,

    *           [],

    *           [],

    *           [bookstore, library],

    *           []

    *           [grocery]

    *        }

    *   Requires: [bookstore, library, grocery]

    *   Output: the best place is 4, to bookstore and lib is 0, and grocery is 2, so in sum is 2.

    * */

 

    public int findBestLocationn(List<Set<String>> road, List<String> requires) {

        Map<String, List<Integer>> roadMap = createMap(road);

        int minSum = Integer.MAX_VALUE, index = 0;

        for (int i = 0; i < road.size(); i++) {

            int sum = 0;

            for (int j = 0; j < requires.size(); j++) {

                sum += getMinLen(roadMap, requires.get(j), i);

            }

            if (sum < minSum) {

                minSum = sum;

                index = i;

            }

        }

        return index;

    }

 

    private Map<String, List<Integer>> createMap(List<Set<String>> road) {

        Map<String, List<Integer>> roadMap = new HashMap<>();

        for (int i = 0; i < road.size(); i++) {

            for (String facility: road.get(i)) {

                List<Integer> list = roadMap.getOrDefault(facility, new ArrayList<>());

                list.add(i);

                roadMap.put(facility, list);

            }

        }

        return null;

    }

 

    private int getMinLen(Map<String, List<Integer>> roadMap, String require, int index) {

        List<Integer> list = roadMap.get(require);

        int minLen = Integer.MAX_VALUE;

        for (int pos: list) {

            minLen = Math.min(minLen, Math.abs(pos-index));

        }

        return minLen;

    }