1912_设计电影租借系统.md

设计电影租借系统

1912. 设计电影租借系统 - 力扣（LeetCode） (leetcode-cn.com)

分析

1. Search操作

要求返回指定电影最便宜的5个：

• 可以使用Map来储存电影信息，键为电影名，值为电影对应的商店的entry列表。
• 要求返回最便宜的5个，使用优先队列储存entry列表。排序关键字为price和shop。
• 遍历优先队列，如果没有借出，加入返回数组。

2. Rent、Drop、Report操作

Rent操作提供shop和movie。

• 为了更快捷的找到电影信息，可以使用一个数组用于储存shop相关信息，每个shop使用哈希表来储存movie和entry的记录。
• 因为Report操作需要返回已经租借的价格最便宜个5个电影信息，所以可以用优先队列来储存已经借出的电影entry，排序关键字为price、shop和movie。
• 为了不修改Search操作中Map，可以使用一个Set来储存已经租借的相关电影entry。
• Drop操作直接删除相关entry在set和rent中的记录即可。

3. 相关数据结构

// 电影信息
Map<Integer, PriorityQueue<int[]>> movies;
// 租借电影信息
Set<int[]> set;
PriorityQueue<int[]> rent;
// 商店信息
Map<Integer, int[]>[] shops;

Java代码

class MovieRentingSystem {
    Map<Integer, PriorityQueue<int[]>> movies;
    Set<int[]> set;
    PriorityQueue<int[]> rent;
    Map<Integer, int[]>[] shops;

    // entry: 0-shop, 1-movie, 2-price
    public MovieRentingSystem(int n, int[][] entries) {
        movies = new HashMap<>();
        set = new HashSet<>();
        rent = new PriorityQueue<>((a, b) -> {
            if (a[2] != b[2]) return a[2] - b[2];
            else if (a[0] != b[0]) return a[0] - b[0];
            else return a[1] - b[1];
        });
        shops = new Map[n];
        for (int i = 0; i < n; i++) shops[i] = new HashMap<>();
        for (int[] entry : entries) {
            if (!movies.containsKey(entry[1]))
                movies.put(entry[1], new PriorityQueue<>((a, b) -> {
                    if (a[2] != b[2]) return a[2] - b[2];
                    else return a[0] - b[0];
                }));
            movies.get(entry[1]).offer(entry);
            shops[entry[0]].put(entry[1], entry);
        }
    }

    public List<Integer> search(int movie) {
        List<Integer> res = new ArrayList<>();
        if (!movies.containsKey(movie)) return res;
        List<int[]> list = new ArrayList<>();
        PriorityQueue<int[]> queue = movies.get(movie);
        for (int i = 0; i < 5 && !queue.isEmpty(); i++) {
            int[] entry = queue.poll();
            list.add(entry);
            if (!set.contains(entry)) res.add(entry[0]);
            else i--;
        }
        for (int[] entry: list) queue.offer(entry);
        return res;
    }

    public void rent(int shop, int movie) {
        int[] entry = shops[shop].get(movie);
        set.add(entry);
        rent.offer(entry);
    }

    public void drop(int shop, int movie) {
        int[] entry = shops[shop].get(movie);
        set.remove(entry);
        rent.remove(entry);
    }

    public List<List<Integer>> report() {
        List<List<Integer>> report = new ArrayList<>();
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < 5 && !rent.isEmpty(); i++) {
            int[] entry = rent.poll();
            list.add(entry);
            report.add(new ArrayList<>(Arrays.asList(entry[0], entry[1])));
        }
        for (int[] entry: list) rent.add(entry);
        return report;
    }
}