最近的房间

最近的房间(hard)

做题过程

只想到用模拟做，还没写完。

算法概述

本题要求为给出两个个数组，第一个数组内部的数组元素包含每个房间的房间号和大小等信息，第二个数组内的数组元素包含要求的房间号和至少的房间大小，计算对于第二个数组中的每个要求，返回最符合条件的房间号（房间号大小偏差最小以及大小要大于等于要求的大小）。使用 离线算法 统一读取查询数组（第二个数组），同时处理两个数组的操作。

时间复杂度为 $O((n+q) \log(n+q))$ ：排序和TreeSet所需要
空间复杂度为O(n+q)：TreeSet所需

JAVA

// 实现Comparable接口（无默认实现）
class Event implements Comparable<Event> {
    /**
     * type     用于区分是查询还是房间
     * size     表示房间大小
     * id       表示房间号
     * origin   表示原始顺序
     */
    int type, size, id, origin;

    public Event(int type, int size, int id, int origin) {
        this.type = type;
        this.size = size;
        this.id = id;
        this.origin = origin;
    }

    @Override
    public int compareTo(Event that) {
      
        if (this.size != that.size) {
            // 更大的优先级更高
            return Integer.compare(that.size, this.size);
        } else {
            // 房间事件优先级更高
            return Integer.compare(this.type, that.type);
        }
    }
}

class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        int m = rooms.length;
        int n = queries.length;

        // 创建事件列表，存储房间和询问事件
        List<Event> events = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            // 房间事件
            events.add(new Event(0, rooms[i][1], rooms[i][0], i));
        }
        for (int i = 0; i < n; ++i) {
            // 询问事件
            events.add(new Event(1, queries[i][1], queries[i][0], i));
        }
        // 对事件列表进行排序（自动选取重写的比较器）
        Collections.sort(events);
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        // 基于红黑树实现（有序），用于存储房间号
        TreeSet<Integer> valid = new TreeSet<>();

        for (Event event : events) {
            if (event.type == 0) {
                // 房间事件，将 roomId 加入有序集合
                valid.add(event.id);
            } else {
                // 询问事件，查找最近的房间
                Integer higher = valid.ceiling(event.id);
                Integer lower = valid.floor(event.id);
                int dist = Integer.MAX_VALUE;

                // 查找最小的大于等于 preferred 的元素
                if (higher != null && higher - event.id < dist) {
                    dist = higher - event.id;
                    ans[event.origin] = higher;
                }
                // 查找最大的严格小于 preferred 的元素
                if (lower != null && event.id - lower <= dist) {
                    ans[event.origin] = lower;
                }
            }
        }

        return ans; 
    }
}

if (higher != null && higher - event.id < dist)和if (lower != null && event.id - lower <= dist)是不同的，正是需要满足在相等情况下，取较小的房间号
TreeSet<Integer> valid = new TreeSet<>();必须这么声明，因为ceiling和floor是TreeSet接口的，而不是Set接口内的

重要实例方法及属性(JAVA)

TreeSet.ceiling(e)：返回大于等于参数的最小元素
TreeSet.floor(e)：返回小于等于参数的最大元素

以上函数实现自NavigableSet接口，除TreeSet以外还有oncurrentSkipListSet也实现了该接口。

总结

离线算法 的核心就在于既然不需要动态读取输入/查询，那么也就意味着已经明确了 参数的规律 ，那么就可以通过统一读取参数来 避免重复遍历 ，比较类似于堆，但是 堆不支持更复杂的条件筛选 。或者说，应该把重心放在 原始下标之外 ，创建一种新的关系映射，也就是 用房间大小作为比较的参数 ，这样就容易得到 无法匹配的查询 ，并且通过这种比较动态插入元素，每次操作的时间复杂度也会大大降低。

需要熟练掌握离线算法对于构造新关系的思想。