双周赛 1942 The Number of the Small

这道题在周赛的时候难到我了，不过赛后总结的时候发现我思路是没问题的，我总需要一个数据结构来存储结果需要的状态
就比如说这道题，他最终需要返回的是你目标人到的时候要做的椅子的位置。
而椅子的位置是由先来后到决定的，但是你不能直接对原数组进行排序，因为你要目标人的index（也就是在原数组中的位置），所以你需要一个数据结构能存下所有人到的时间，离开的时间，以及他们的index。 我当时比赛的思路是用hashmap 来存一个数组，代表这个人的到的时间和离开的时间，也就是Map<int[], Integer> 而key对应的value存的是这个人的index
key本身是int[]， int[0] 存的是到的时间，int[1] 存的是离开的时间。
而下面实际上就可以对原数组按照来的时间进行排序了，排好序之后直接iterate这个数组，把先来的人加入priorityqueue， 然后每个人到的时候先把pq里面的人离开时间小于他的都poll离pq。

这时候比较关键的点就来了，你存进pq里面的值需要包含seat。也就是说你每次poll的时候能够读到空出来的seat，然后把seat加回一个数据结构，当时我想用一个boolean[] 或者set来存，但是困住了。
后来再看别人的代码的时候，我发现其实你可以用另一个PQ存seat，而且自动帮你排好序了，也就是你每次从seats 这个priorityqueue 取出来的第一个int 就是你当前能够拿到最小的座位。而你每次有离开的人就把他对应的座位直接存进seats这个pq里面就好了。
下面是代码

    public int smallestChair(int[][] times, int targetFriend) {
        Map<int[], Integer> map = new HashMap<>();
        for (int i = 0; i < times.length; i++) {
            map.put(times[i], i);
        }
        Arrays.sort(times, (a,b) -> (a[0] - b[0]));
        int count = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> (a[1] - b[1]));
        PriorityQueue<Integer> seats = new PriorityQueue<>();
        for (int i = 0; i < times.length; i++) seats.add(i);
        for (int[] cur : times) {
            while (!q.isEmpty() && cur[0] >= q.peek()[1]) {
                // System.out.println(q.peek()[1] + " " + cur[0]);
                int[] leaving = q.poll();
                seats.add(leaving[2]);
            }
            // System.out.println(q.size());
            if (map.get(cur) == targetFriend) {
                // int[] current = q.poll();
                // while(current[0] != cur[0] && current[1] != cur[1]) {
                //     current = q.poll();
                // }
                return seats.poll();
            }
            q.add(new int[] {cur[0], cur[1], seats.poll()});
        }
        return 0;
    }