LeetCode Daily Problem P1912 Design Movie Rental System

---

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 property of set, putting the sorting time into insertion and deletion.

#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 the global data map
  unordered_map<int, unordered_map<int, int>> dmap;
  // map<movie, set<Movie>> map of not rented out
  unordered_map<int, set<Movie>> umap;
  // set<Movies> indicates already rented out
  set<Movie> rented;
  // set<Movies> indicates not rented out
  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;
      // set of not rented
      unrented.insert({shop, movie, price});
      // map of not rented
      umap[movie].insert({{shop, movie, price}});
    }
  }
  // Find the 5 cheapest shops that have the specified movie and have not rented it 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;
  }

  // Rent the specified movie from the specified shop. The problem guarantees that the specified movie is not rented out at the specified shop.
  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 specified movie that was previously rented out to the specified shop
  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 rented-out 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;
}