1912. 设计电影租借系统

题目描述

你有一个电影租借公司和 n 个电影商店。你想要实现一个电影租借系统，它支持查询、预订和返还电影的操作。同时系统还能生成一份当前被借出电影的报告。

所有电影用二维整数数组 entries 表示，其中 entries[i] = [shop_i, movie_i, price_i] 表示商店 shop_i 有一份电影 movie_i 的拷贝，租借价格为 price_i 。每个商店有 至多一份 编号为 movie_i 的电影拷贝。

系统需要支持以下操作：

Search：找到拥有指定电影且 未借出 的商店中 最便宜的 5 个 。商店需要按照价格升序排序，如果价格相同，则 shop_i 较小的商店排在前面。如果查询结果少于 5 个商店，则将它们全部返回。如果查询结果没有任何商店，则返回空列表。
Rent：从指定商店借出指定电影，题目保证指定电影在指定商店 未借出 。
Drop：在指定商店返还 之前已借出 的指定电影。
Report：返回 最便宜的 5 部已借出电影 （可能有重复的电影 ID），将结果用二维列表 res 返回，其中 res[j] = [shop_j, movie_j] 表示第 j 便宜的已借出电影是从商店 shop_j 借出的电影 movie_j 。res 中的电影需要按价格升序排序；如果价格相同，则 shop_j 较小的排在前面；如果仍然相同，则 movie_j 较小的排在前面。如果当前借出的电影小于 5 部，则将它们全部返回。如果当前没有借出电影，则返回一个空的列表。

请你实现 MovieRentingSystem 类：

MovieRentingSystem(int n, int[][] entries) 将 MovieRentingSystem 对象用 n 个商店和 entries 表示的电影列表初始化。
List<Integer> search(int movie) 如上所述，返回 未借出 指定 movie 的商店列表。
void rent(int shop, int movie) 从指定商店 shop 借出指定电影 movie 。
void drop(int shop, int movie) 在指定商店 shop 返还之前借出的电影 movie 。
List<List<Integer>> report() 如上所述，返回最便宜的 已借出 电影列表。

注意：测试数据保证 rent 操作中指定商店拥有 未借出 的指定电影，且 drop 操作指定的商店 之前已借出 指定电影。

示例 1：

输入：
["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]
[[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]]
输出：
[null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]

解释：
MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);
movieRentingSystem.search(1);  // 返回 [1, 0, 2] ，商店 1，0 和 2 有未借出的 ID 为 1 的电影。商店 1 最便宜，商店 0 和 2 价格相同，所以按商店编号排序。
movieRentingSystem.rent(0, 1); // 从商店 0 借出电影 1 。现在商店 0 未借出电影编号为 [2,3] 。
movieRentingSystem.rent(1, 2); // 从商店 1 借出电影 2 。现在商店 1 未借出的电影编号为 [1] 。
movieRentingSystem.report();   // 返回 [[0, 1], [1, 2]] 。商店 0 借出的电影 1 最便宜，然后是商店 1 借出的电影 2 。
movieRentingSystem.drop(1, 2); // 在商店 1 返还电影 2 。现在商店 1 未借出的电影编号为 [1,2] 。
movieRentingSystem.search(2);  // 返回 [0, 1] 。商店 0 和 1 有未借出的 ID 为 2 的电影。商店 0 最便宜，然后是商店 1 。

提示：

1 <= n <= 3 * 10⁵
1 <= entries.length <= 10⁵
0 <= shop_i < n
1 <= movie_i, price_i <= 10⁴
每个商店至多有一份电影 movie_i 的拷贝。
search，rent，drop 和 report 的调用总共不超过 10⁵ 次。

解法

方法一：有序集合

我们定义一个有序集合 \(\textit{available}\)，其中 \(\textit{available}[movie]\) 存储所有未借出的电影 \(movie\) 的商店列表，列表中的元素为 \((\textit{price}, \textit{shop})\)，并按照 \(\textit{price}\) 升序排序，如果 \(\textit{price}\) 相同，则按照 \(\textit{shop}\) 升序排序。

另外定义一个哈希表 \(\textit{price\_map}\)，其中 \(\textit{price\_map}[f(\textit{shop}, \textit{movie})]\) 存储商店 \(\textit{shop}\) 中电影 \(\textit{movie}\) 的租借价格。

我们还定义一个有序集合 \(\textit{rented}\)，其中存储所有已借出的电影，元素为 \((\textit{price}, \textit{shop}, \textit{movie})\)，并按照 \(\textit{price}\) 升序排序，如果 \(\textit{price}\) 相同，则按照 \(\textit{shop}\) 升序排序，如果 \(\textit{shop}\) 也相同，则按照 \(\textit{movie}\) 升序排序。

对于 \(\text{MovieRentingSystem}(n, \text{entries})\) 操作，我们遍历 \(\text{entries}\)，将每个商店的电影信息加入到 \(\textit{available}\) 和 \(\textit{price\_map}\) 中。时间复杂度为 \(O(m \log m)\)，其中 \(m\) 是 \(\text{entries}\) 的长度。

对于 \(\text{search}(\text{movie})\) 操作，我们返回 \(\textit{available}[\text{movie}]\) 中前 5 个商店的编号。时间复杂度为 \(O(1)\)。

对于 \(\text{rent}(\text{shop}, \text{movie})\) 操作，我们从 \(\textit{available}[\text{movie}]\) 中移除 \((\textit{price}, \textit{shop})\)，并将 \((\textit{price}, \textit{shop}, \textit{movie})\) 加入到 \(\textit{rented}\) 中。时间复杂度为 \(O(\log m)\)。

对于 \(\text{drop}(\text{shop}, \text{movie})\) 操作，我们从 \(\textit{rented}\) 中移除 \((\textit{price}, \textit{shop}, \textit{movie})\)，并将 \((\textit{price}, \textit{shop})\) 加入到 \(\textit{available}[\text{movie}]\) 中。时间复杂度为 \(O(\log m)\)。

对于 \(\text{report}()\) 操作，我们返回 \(\textit{rented}\) 中前 5 个已借出电影的商店编号和电影编号。时间复杂度为 \(O(1)\)。

空间复杂度为 \(O(m)\)。其中 \(m\) 是 \(\text{entries}\) 的长度。

Python3JavaC++Go

class MovieRentingSystem:

    def __init__(self, n: int, entries: List[List[int]]):
        self.available = defaultdict(lambda: SortedList())
        self.price_map = {}
        for shop, movie, price in entries:
            self.available[movie].add((price, shop))
            self.price_map[self.f(shop, movie)] = price
        self.rented = SortedList()

    def search(self, movie: int) -> List[int]:
        return [shop for _, shop in self.available[movie][:5]]

    def rent(self, shop: int, movie: int) -> None:
        price = self.price_map[self.f(shop, movie)]
        self.available[movie].remove((price, shop))
        self.rented.add((price, shop, movie))

    def drop(self, shop: int, movie: int) -> None:
        price = self.price_map[self.f(shop, movie)]
        self.rented.remove((price, shop, movie))
        self.available[movie].add((price, shop))

    def report(self) -> List[List[int]]:
        return [[shop, movie] for _, shop, movie in self.rented[:5]]

    def f(self, shop: int, movie: int) -> int:
        return shop << 30 | movie


# Your MovieRentingSystem object will be instantiated and called as such:
# obj = MovieRentingSystem(n, entries)
# param_1 = obj.search(movie)
# obj.rent(shop,movie)
# obj.drop(shop,movie)
# param_4 = obj.report()

class MovieRentingSystem {
    private Map<Integer, TreeSet<int[]>> available = new HashMap<>();
    private Map<Long, Integer> priceMap = new HashMap<>();
    private TreeSet<int[]> rented = new TreeSet<>((a, b) -> {
        if (a[0] != b[0]) {
            return a[0] - b[0];
        }
        if (a[1] != b[1]) {
            return a[1] - b[1];
        }
        return a[2] - b[2];
    });

    public MovieRentingSystem(int n, int[][] entries) {
        for (int[] entry : entries) {
            int shop = entry[0], movie = entry[1], price = entry[2];
            available
                .computeIfAbsent(movie, k -> new TreeSet<>((a, b) -> {
                    if (a[0] != b[0]) {
                        return a[0] - b[0];
                    }
                    return a[1] - b[1];
                }))
                .add(new int[] {price, shop});
            priceMap.put(f(shop, movie), price);
        }
    }

    public List<Integer> search(int movie) {
        List<Integer> res = new ArrayList<>();
        if (!available.containsKey(movie)) {
            return res;
        }
        int cnt = 0;
        for (int[] item : available.get(movie)) {
            res.add(item[1]);
            if (++cnt == 5) {
                break;
            }
        }
        return res;
    }

    public void rent(int shop, int movie) {
        int price = priceMap.get(f(shop, movie));
        available.get(movie).remove(new int[] {price, shop});
        rented.add(new int[] {price, shop, movie});
    }

    public void drop(int shop, int movie) {
        int price = priceMap.get(f(shop, movie));
        rented.remove(new int[] {price, shop, movie});
        available.get(movie).add(new int[] {price, shop});
    }

    public List<List<Integer>> report() {
        List<List<Integer>> res = new ArrayList<>();
        int cnt = 0;
        for (int[] item : rented) {
            res.add(Arrays.asList(item[1], item[2]));
            if (++cnt == 5) {
                break;
            }
        }
        return res;
    }

    private long f(int shop, int movie) {
        return ((long) shop << 30) | movie;
    }
}

/**
 * Your MovieRentingSystem object will be instantiated and called as such:
 * MovieRentingSystem obj = new MovieRentingSystem(n, entries);
 * List<Integer> param_1 = obj.search(movie);
 * obj.rent(shop,movie);
 * obj.drop(shop,movie);
 * List<List<Integer>> param_4 = obj.report();
 */

class MovieRentingSystem {
private:
    unordered_map<int, set<pair<int, int>>> available; // movie -> {(price, shop)}
    unordered_map<long long, int> priceMap;
    set<tuple<int, int, int>> rented; // {(price, shop, movie)}

    long long f(int shop, int movie) {
        return ((long long) shop << 30) | movie;
    }

public:
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for (auto& e : entries) {
            int shop = e[0], movie = e[1], price = e[2];
            available[movie].insert({price, shop});
            priceMap[f(shop, movie)] = price;
        }
    }

    vector<int> search(int movie) {
        vector<int> res;
        if (!available.count(movie)) {
            return res;
        }
        int cnt = 0;
        for (auto& [price, shop] : available[movie]) {
            res.push_back(shop);
            if (++cnt == 5) {
                break;
            }
        }
        return res;
    }

    void rent(int shop, int movie) {
        int price = priceMap[f(shop, movie)];
        available[movie].erase({price, shop});
        rented.insert({price, shop, movie});
    }

    void drop(int shop, int movie) {
        int price = priceMap[f(shop, movie)];
        rented.erase({price, shop, movie});
        available[movie].insert({price, shop});
    }

    vector<vector<int>> report() {
        vector<vector<int>> res;
        int cnt = 0;
        for (auto& [price, shop, movie] : rented) {
            res.push_back({shop, movie});
            if (++cnt == 5) {
                break;
            }
        }
        return res;
    }
};

/**
 * Your MovieRentingSystem object will be instantiated and called as such:
 * MovieRentingSystem* obj = new MovieRentingSystem(n, entries);
 * vector<int> param_1 = obj->search(movie);
 * obj->rent(shop,movie);
 * obj->drop(shop,movie);
 * vector<vector<int>> param_4 = obj->report();
 */

type MovieRentingSystem struct {
    available map[int]*treeset.Set // movie -> (price, shop)
    priceMap  map[int64]int
    rented    *treeset.Set // (price, shop, movie)
}

func Constructor(n int, entries [][]int) MovieRentingSystem {
    // comparator for (price, shop)
    cmpAvail := func(a, b any) int {
        x := a.([2]int)
        y := b.([2]int)
        if x[0] != y[0] {
            return x[0] - y[0]
        }
        return x[1] - y[1]
    }
    // comparator for (price, shop, movie)
    cmpRented := func(a, b any) int {
        x := a.([3]int)
        y := b.([3]int)
        if x[0] != y[0] {
            return x[0] - y[0]
        }
        if x[1] != y[1] {
            return x[1] - y[1]
        }
        return x[2] - y[2]
    }

    mrs := MovieRentingSystem{
        available: make(map[int]*treeset.Set),
        priceMap:  make(map[int64]int),
        rented:    treeset.NewWith(cmpRented),
    }

    for _, e := range entries {
        shop, movie, price := e[0], e[1], e[2]
        if _, ok := mrs.available[movie]; !ok {
            mrs.available[movie] = treeset.NewWith(cmpAvail)
        }
        mrs.available[movie].Add([2]int{price, shop})
        mrs.priceMap[f(shop, movie)] = price
    }

    return mrs
}

func (this *MovieRentingSystem) Search(movie int) []int {
    res := []int{}
    if _, ok := this.available[movie]; !ok {
        return res
    }
    it := this.available[movie].Iterator()
    it.Begin()
    cnt := 0
    for it.Next() && cnt < 5 {
        pair := it.Value().([2]int)
        res = append(res, pair[1])
        cnt++
    }
    return res
}

func (this *MovieRentingSystem) Rent(shop int, movie int) {
    price := this.priceMap[f(shop, movie)]
    this.available[movie].Remove([2]int{price, shop})
    this.rented.Add([3]int{price, shop, movie})
}

func (this *MovieRentingSystem) Drop(shop int, movie int) {
    price := this.priceMap[f(shop, movie)]
    this.rented.Remove([3]int{price, shop, movie})
    this.available[movie].Add([2]int{price, shop})
}

func (this *MovieRentingSystem) Report() [][]int {
    res := [][]int{}
    it := this.rented.Iterator()
    it.Begin()
    cnt := 0
    for it.Next() && cnt < 5 {
        t := it.Value().([3]int)
        res = append(res, []int{t[1], t[2]})
        cnt++
    }
    return res
}

func f(shop, movie int) int64 {
    return (int64(shop) << 30) | int64(movie)
}

/**
 * Your MovieRentingSystem object will be instantiated and called as such:
 * obj := Constructor(n, entries);
 * param_1 := obj.Search(movie);
 * obj.Rent(shop,movie);
 * obj.Drop(shop,movie);
 * param_4 := obj.Report();
 */

1912. 设计电影租借系统

题目描述

解法

方法一：有序集合

评论