Cover image for LeetCode Daily Problem P1912 Design Movie Rental System

LeetCode Daily Problem P1912 Design Movie Rental System

(Updated: )
algorithm
, ,
Timeline

Timeline

2025-09-21

init

unordered_map, set

Problem:

p1912 Design Movie Rental System

https://leetcode.cn/problems/design-movie-rental-system/description/?envType=daily-question&envId=2025-09-21

The n shops given in the problem are not used. The main idea is to use the ordering of sets, putting the sorting time into insertions and deletions.

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <set>
#include <unordered_map>
#include <vector>

using std::set;
using std::unordered_map;
using std::vector;

class Movie {
public:
  int shop;
  int movie;
  int price;

  bool operator<(const Movie &other) const {
    if (price != other.price)
      return price < other.price;
    if (shop != other.shop)
      return shop < other.shop;
    return movie < other.movie;
  }
};

class MovieRentingSystem {
private:
  // map<movies, map<shop,price>> stores global data map
  unordered_map<int, unordered_map<int, int>> dmap;
  // map<movie, set<Movie>> Unrented map
  unordered_map<int, set<Movie>> umap;
  // set<Movies>indicates already rented
  set<Movie> rented;
  // set<Movies>indicates not rented
  set<Movie> unrented;

  int shop_num;

public:
  // [shopi, moviei, pricei]
  MovieRentingSystem(int n, vector<vector<int>> &entries) {
    int shop, movie, price;
    shop_num = n;
    for (vector<int> vec : entries) {
      shop = vec[0];
      movie = vec[1];
      price = vec[2];
      // Global data
      dmap[movie][shop] = price;
      // Unrented set
      unrented.insert({shop, movie, price});
      // Unrented map
      umap[movie].insert({{shop, movie, price}});
    }
  }
  // Find the 5 cheapest stores that have the specified movie and where it is not lent out
  vector<int> search(int movie) {
    vector<int> res;
    set<Movie> &tmp_set = umap[movie];
    int cnt = 0;
    for (auto it = tmp_set.begin(); it != tmp_set.end() && cnt < 5;
         it++, cnt++) {
      res.push_back(it->shop);
    }
    return res;
  }

  // Borrow the specified movie from the specified store, the problem guarantees that the specified movie is not lent out at the specified store
  void rent(int shop, int movie) {
    int price = dmap[movie][shop];
    rented.insert({shop, movie, price});
    unrented.erase({shop, movie, price});
    umap[movie].erase({shop, movie, price});
    if (umap[movie].empty()) {
      umap.erase(movie);
    }
  }
  // Return the previously borrowed specified movie at the specified store
  void drop(int shop, int movie) {
    int price = dmap[movie][shop];
    unrented.insert({shop, movie, price});
    rented.erase({shop, movie, price});
    umap[movie].insert({shop, movie, price});
  }
  // Return the 5 cheapest borrowed movies (movie IDs may be duplicated)
  vector<vector<int>> report() {
    vector<vector<int>> res;
    int cnt = 0;
    for (auto it = rented.begin(); it != rented.end() && cnt < 5; it++, cnt++) {
      vector<int> vec;
      vec.push_back(it->shop);
      vec.push_back(it->movie);
      res.push_back(vec);
    }
    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();
 */

#include <iostream>
#include <string>
using std::cout;
using std::endl;
using std::string;

// Output helper function
static string vec_to_str(const vector<int> &v) {
  string s = "[";
  for (size_t i = 0; i < v.size(); ++i) {
    s += std::to_string(v[i]);
    if (i + 1 != v.size())
      s += ",";
  }
  s += "]";
  return s;
}
static string mat_to_str(const vector<vector<int>> &m) {
  string s = "[";
  for (size_t i = 0; i < m.size(); ++i) {
    s += vec_to_str(m[i]);
    if (i + 1 != m.size())
      s += ", ";
  }
  s += "]";
  return s;
}

int main() {
  vector<vector<int>> entries = {{0, 1, 5}, {0, 2, 6}, {0, 3, 7},
                                 {1, 1, 4}, {1, 2, 7}, {2, 1, 5}};
  vector<string> outputs;
  outputs.push_back("null");
  MovieRentingSystem obj(3, entries);

  // search(1)
  outputs.push_back(vec_to_str(obj.search(1)));
  // rent(0,1)
  obj.rent(0, 1);
  outputs.push_back("null");
  // rent(1,2)
  obj.rent(1, 2);
  outputs.push_back("null");
  // report()
  outputs.push_back(mat_to_str(obj.report()));
  // drop(1,2)
  obj.drop(1, 2);
  outputs.push_back("null");
  // search(2)
  outputs.push_back(vec_to_str(obj.search(2)));

  // Print the final result
  cout << "[";
  for (size_t i = 0; i < outputs.size(); ++i) {
    cout << outputs[i];
    if (i + 1 != outputs.size())
      cout << ", ";
  }
  cout << "]\n";
  return 0;
}