Design Movie Rental System LeetCode solution in C++

1
int speedup = [] {
2
  ios::sync_with_stdio(0);
3
  cin.tie(0);
4
  return 0;
5
}();
6

7
class MovieRentingSystem {
8
 public:
9
#define pppi pair<int, pair<int, int>>
10

11
  set<pppi> unrented, rented;
12

13
  map<pair<int, int>, int> mp;
14

15
  // facilitates search by storing the prices and shops a particular movie is
16
  // associated with
17
  unordered_map<int, set<pair<int, int>>> movies;
18

19
  MovieRentingSystem(int n, vector<vector<int>> &entries) {
20
    for (int i = 0; i < entries.size(); i++) {
21
      int shop = entries[i][0];
22
      int movie = entries[i][1];
23
      int price = entries[i][2];
24

25
      // initially all movies are unrented
26
      unrented.insert({price, {shop, movie}});
27

28
      // store the price for each pair of {shop,movie}. remember this pair is
29
      // unique as given in the problem statement
30
      mp[{shop, movie}] = price;
31

32
      // store all the movies with their price and shop
33
      movies[movie].insert({price, shop});
34
    }
35
  }
36

37
  vector<int> search(int movie) {
38
    // return a list of 5 cheapest shops that have the given movie
39

40
    vector<int> ans;
41

42
    for (auto x : movies[movie]) {
43
      if ((int)ans.size() == 5) break;
44

45
      ans.push_back(x.second);
46
    }
47

48
    return ans;
49
  }
50

51
  void rent(int shop, int movie) {
52
    // remove the movie from the given shop
53

54
    int price = mp[{shop, movie}];
55

56
    // add this movie in rented
57
    rented.insert({price, {shop, movie}});
58

59
    // remove this movie from unrented
60
    unrented.erase({price, {shop, movie}});
61

62
    // also, erase this shop from the movies, since this movie will be no longer
63
    // present in the given shop
64
    movies[movie].erase(movies[movie].find({price, shop}));
65
  }
66

67
  void drop(int shop, int movie) {
68
    // return or add
69

70
    int price = mp[{shop, movie}];
71

72
    // add in unrented as movie is back in the shop
73
    unrented.insert({price, {shop, movie}});
74

75
    movies[movie].insert({price, shop});
76

77
    // remove from rented
78
    rented.erase({price, {shop, movie}});
79
  }
80

81
  vector<vector<int>> report() {
82
    // return the 5 cheapest rented movies as {shop, movie}
83

84
    // here comes the use of rented data structure, since we can quickly select
85
    // 5 cheapest movies that are rented
86
    vector<vector<int>> ans;
87

88
    for (auto x : rented) {
89
      if (ans.size() == 5) break;
90

91
      int shop = x.second.first;
92
      int movie = x.second.second;
93

94
      ans.push_back({shop, movie});
95
    }
96
    return ans;
97
  }
98
};
99

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