Skip to content

1912. Design Movie Rental System 👍

  • Time:
    • Constructor: $O(n\log n)$
    • search(movie: int): $O(\log n)$
    • rent(shop: int, movie: int): $O(\log n)$
    • drop(shop: int, movie: int): $O(\log n)$
    • report(): $O(\log n)$
  • Space: $O(n + |\texttt{rent()}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class MovieRentingSystem {
 public:
  MovieRentingSystem(int n, vector<vector<int>>& entries) {
    for (const vector<int>& e : entries) {
      const int shop = e[0];
      const int movie = e[1];
      const int price = e[2];
      unrented[movie].insert({price, shop});
      shopAndMovieToPrice[{shop, movie}] = price;
    }
  }

  vector<int> search(int movie) {
    vector<int> ans;
    int i = 0;

    for (const auto& [price, shop] : unrented[movie]) {
      ans.push_back(shop);
      if (++i >= 5)
        break;
    }

    return ans;
  }

  void rent(int shop, int movie) {
    const int price = shopAndMovieToPrice[{shop, movie}];
    unrented[movie].erase({price, shop});
    rented.insert({price, {shop, movie}});
  }

  void drop(int shop, int movie) {
    const int price = shopAndMovieToPrice[{shop, movie}];
    unrented[movie].insert({price, shop});
    rented.erase({price, {shop, movie}});
  }

  vector<vector<int>> report() {
    vector<vector<int>> ans;
    int i = 0;

    for (const auto& [_, shopAndMovie] : rented) {
      ans.push_back({shopAndMovie.first, shopAndMovie.second});
      if (++i >= 5)
        break;
    }

    return ans;
  }

 private:
  struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
      return p.first ^ p.second;
    }
  };

  // {movie: (price, shop)}
  unordered_map<int, set<pair<int, int>>> unrented;

  // {(shop, movie): price}
  unordered_map<pair<int, int>, int, PairHash> shopAndMovieToPrice;

  // (price, (shop, movie))
  set<pair<int, pair<int, int>>> rented;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class MovieRentingSystem {
  public MovieRentingSystem(int n, int[][] entries) {
    for (int[] e : entries) {
      final int shop = e[0];
      final int movie = e[1];
      final int price = e[2];
      unrented.putIfAbsent(movie, new TreeSet<>(comparator));
      unrented.get(movie).add(new Entry(price, shop, movie));
      shopAndMovieToPrice.put(new Pair<>(shop, movie), price);
    }
  }

  public List<Integer> search(int movie) {
    return unrented.getOrDefault(movie, Collections.emptySet())
        .stream()
        .limit(5)
        .map(e -> e.shop)
        .collect(Collectors.toList());
  }

  public void rent(int shop, int movie) {
    final int price = shopAndMovieToPrice.get(new Pair<>(shop, movie));
    unrented.get(movie).remove(new Entry(price, shop, movie));
    rented.add(new Entry(price, shop, movie));
  }

  public void drop(int shop, int movie) {
    final int price = shopAndMovieToPrice.get(new Pair<>(shop, movie));
    unrented.get(movie).add(new Entry(price, shop, movie));
    rented.remove(new Entry(price, shop, movie));
  }

  public List<List<Integer>> report() {
    return rented.stream().limit(5).map(e -> List.of(e.shop, e.movie)).collect(Collectors.toList());
  }

  private record Entry(int price, int shop, int movie) {}

  private Comparator<Entry> comparator = (a, b) -> {
    if (a.price != b.price)
      return Integer.compare(a.price, b.price);
    if (a.shop != b.shop)
      return Integer.compare(a.shop, b.shop);
    return Integer.compare(a.movie, b.movie);
  };

  // {movie: (price, shop)}
  private Map<Integer, Set<Entry>> unrented = new HashMap<>();

  // {(shop, movie): price}
  private Map<Pair<Integer, Integer>, Integer> shopAndMovieToPrice = new HashMap<>();

  // (price, shop, movie)
  private Set<Entry> rented = new TreeSet<>(comparator);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from sortedcontainers import SortedList


class MovieRentingSystem:
  def __init__(self, n: int, entries: list[list[int]]):
    self.unrented = collections.defaultdict(
        SortedList)  # {movie: (price, shop)}
    self.shopAndMovieToPrice = {}  # {(shop, movie): price}
    self.rented = SortedList()  # (price, shop, movie)
    for shop, movie, price in entries:
      self.unrented[movie].add((price, shop))
      self.shopAndMovieToPrice[(shop, movie)] = price

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

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

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

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