Posts tagged as “treeset”

花花酱 LeetCode 1912. Design Movie Rental System

By zxi on January 1, 2022

You have a movie renting company consisting of n shops. You want to implement a renting system that supports searching for, booking, and returning movies. The system should also support generating a report of the currently rented movies.

Each movie is given as a 2D integer array entries where entries[i] = [shop_i, movie_i, price_i] indicates that there is a copy of movie movie_i at shop shop_i with a rental price of price_i. Each shop carries at most one copy of a movie movie_i.

The system should support the following functions:

Search: Finds the cheapest 5 shops that have an unrented copy of a given movie. The shops should be sorted by price in ascending order, and in case of a tie, the one with the smaller shop_i should appear first. If there are less than 5 matching shops, then all of them should be returned. If no shop has an unrented copy, then an empty list should be returned.
Rent: Rents an unrented copy of a given movie from a given shop.
Drop: Drops off a previously rented copy of a given movie at a given shop.
Report: Returns the cheapest 5 rented movies (possibly of the same movie ID) as a 2D list res where res[j] = [shop_j, movie_j] describes that the j^th cheapest rented movie movie_j was rented from the shop shop_j. The movies in res should be sorted by price in ascending order, and in case of a tie, the one with the smaller shop_j should appear first, and if there is still tie, the one with the smaller movie_j should appear first. If there are fewer than 5 rented movies, then all of them should be returned. If no movies are currently being rented, then an empty list should be returned.

Implement the MovieRentingSystem class:

MovieRentingSystem(int n, int[][] entries) Initializes the MovieRentingSystem object with n shops and the movies in entries.
List<Integer> search(int movie) Returns a list of shops that have an unrented copy of the given movie as described above.
void rent(int shop, int movie) Rents the given movie from the given shop.
void drop(int shop, int movie) Drops off a previously rented movie at the given shop.
List<List<Integer>> report() Returns a list of cheapest rented movies as described above.

Note: The test cases will be generated such that rent will only be called if the shop has an unrented copy of the movie, and drop will only be called if the shop had previously rented out the movie.

Example 1:

Input
["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]]
Output
[null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]

Explanation
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);  // return [1, 0, 2], Movies of ID 1 are unrented at shops 1, 0, and 2. Shop 1 is cheapest; shop 0 and 2 are the same price, so order by shop number.
movieRentingSystem.rent(0, 1); // Rent movie 1 from shop 0. Unrented movies at shop 0 are now [2,3].
movieRentingSystem.rent(1, 2); // Rent movie 2 from shop 1. Unrented movies at shop 1 are now [1].
movieRentingSystem.report();   // return [[0, 1], [1, 2]]. Movie 1 from shop 0 is cheapest, followed by movie 2 from shop 1.
movieRentingSystem.drop(1, 2); // Drop off movie 2 at shop 1. Unrented movies at shop 1 are now [1,2].
movieRentingSystem.search(2);  // return [0, 1]. Movies of ID 2 are unrented at shops 0 and 1. Shop 0 is cheapest, followed by shop 1.

Constraints:

1 <= n <= 3 * 10⁵
1 <= entries.length <= 10⁵
0 <= shop_i < n
1 <= movie_i, price_i <= 10⁴
Each shop carries at most one copy of a movie movie_i.
At most 10⁵ calls in total will be made to search, rent, drop and report.

Solution: Hashtable + TreeSet

We need three containers:
1. movies tracks the {movie -> price} of each shop. This is readonly to get the price of a movie for generating keys for treesets.
2. unrented tracks unrented movies keyed by movie id, value is a treeset ordered by {price, shop}.
3. rented tracks rented movies, a treeset ordered by {price, shop, movie}

Note: By using array<int, 3> we can unpack values like below:
array<int, 3> entries; // {price, shop, movie}
for (const auto [price, shop, moive] : entries)
…

Time complexity:
Init: O(nlogn)
rent / drop: O(logn)
search / report: O(1)

Space complexity: O(n)

C++

// Author: Huahua

class MovieRentingSystem {

public:

MovieRentingSystem(int n, vector<vector<int>>& entries): movies(n) {

for (const auto& e : entries) {

const int shop = e[0];

const int movie = e[1];

const int price = e[2];

movies[shop].emplace(movie, price);

unrented[movie].emplace(price, shop);

}

vector<int> search(int movie) {

vector<int> shops;

for (const auto [price, shop] : unrented[movie]) {

shops.push_back(shop);

if (shops.size() == 5) break;

}

return shops;

}

void rent(int shop, int movie) {

const int price = movies[shop][movie];

unrented[movie].erase({price, shop});

rented.insert({price, shop, movie});

}

void drop(int shop, int movie) {

const int price = movies[shop][movie];

rented.erase({price, shop, movie});

unrented[movie].emplace(price, shop);

}

vector<vector<int>> report() {

vector<vector<int>> ans;

for (const auto& [price, shop, movie] : rented) {

ans.push_back({shop, movie});

if (ans.size() == 5) break;

}

return ans;

}

private:

vector<unordered_map<int, int>> movies; // shop -> {movie -> price}

unordered_map<int, set<pair<int, int>>> unrented; // movie -> {price, shop}

set<array<int, 3>> rented; // {price, shop, movie}

};

花花酱 LeetCode 1942. The Number of the Smallest Unoccupied Chair

By zxi on December 31, 2021

There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity. When a friend arrives at the party, they sit on the unoccupied chair with the smallest number.

For example, if chairs 0, 1, and 5 are occupied when a friend comes, they will sit on chair number 2.

When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.

You are given a 0-indexed 2D integer array times where times[i] = [arrival_i, leaving_i], indicating the arrival and leaving times of the i^th friend respectively, and an integer targetFriend. All arrival times are distinct.

Return the chair number that the friend numbered targetFriend will sit on.

Example 1:

Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1
Explanation: 
- Friend 0 arrives at time 1 and sits on chair 0.
- Friend 1 arrives at time 2 and sits on chair 1.
- Friend 1 leaves at time 3 and chair 1 becomes empty.
- Friend 0 leaves at time 4 and chair 0 becomes empty.
- Friend 2 arrives at time 4 and sits on chair 0.
Since friend 1 sat on chair 1, we return 1.

Example 2:

Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0
Output: 2
Explanation: 
- Friend 1 arrives at time 1 and sits on chair 0.
- Friend 2 arrives at time 2 and sits on chair 1.
- Friend 0 arrives at time 3 and sits on chair 2.
- Friend 1 leaves at time 5 and chair 0 becomes empty.
- Friend 2 leaves at time 6 and chair 1 becomes empty.
- Friend 0 leaves at time 10 and chair 2 becomes empty.
Since friend 0 sat on chair 2, we return 2.

Constraints:

n == times.length
2 <= n <= 10⁴
times[i].length == 2
1 <= arrival_i < leaving_i <= 10⁵
0 <= targetFriend <= n - 1
Each arrival_i time is distinct.

Solution: Treeset + Simulation

Use a treeset to track available chairs, sort events by time.
note: process leaving events first.

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int smallestChair(vector<vector<int>>& times, int targetFriend) {

const int n = times.size();

vector<pair<int, int>> arrival(n);

vector<pair<int, int>> leaving(n);

for (int i = 0; i < n; ++i) {

arrival[i] = {times[i][0], i};

leaving[i] = {times[i][1], i};

}

vector<int> pos(n);

iota(begin(pos), end(pos), 0); // pos = [0, 1, ..., n -1]

set<int> aval(begin(pos), end(pos));

sort(begin(arrival), end(arrival));

sort(begin(leaving), end(leaving));

for (int i = 0, j = 0; i < n; ++i) {

const auto [t, u] = arrival[i];

while (j < n && leaving[j].first <= t)

aval.insert(pos[leaving[j++].second]);

aval.erase(pos[u] = *begin(aval));

if (u == targetFriend) return pos[u];

}

return -1;

}

};

花花酱 LeetCode 2102. Sequentially Ordinal Rank Tracker

By zxi on December 12, 2021

A scenic location is represented by its name and attractiveness score, where name is a unique string among all locations and score is an integer. Locations can be ranked from the best to the worst. The higher the score, the better the location. If the scores of two locations are equal, then the location with the lexicographically smaller name is better.

You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:

Adding scenic locations, one at a time.
Querying the i^th best location of all locations already added, where i is the number of times the system has been queried (including the current query).
- For example, when the system is queried for the 4^th time, it returns the 4^th best location of all locations already added.

Note that the test data are generated so that at any time, the number of queries does not exceed the number of locations added to the system.

Implement the SORTracker class:

SORTracker() Initializes the tracker system.
void add(string name, int score) Adds a scenic location with name and score to the system.
string get() Queries and returns the i^th best location, where i is the number of times this method has been invoked (including this invocation).

Example 1:

Input

["SORTracker", "add", "add", "get", "add", "get", "add", "get", "add", "get", "add", "get", "get"]

[[], ["bradford", 2], ["branford", 3], [], ["alps", 2], [], ["orland", 2], [], ["orlando", 3], [], ["alpine", 2], [], []]

Output

[null, null, null, "branford", null, "alps", null, "bradford", null, "bradford", null, "bradford", "orland"]

Explanation

SORTracker tracker = new SORTracker(); // Initialize the tracker system.

tracker.add("bradford", 2); // Add location with name="bradford" and score=2 to the system.

tracker.add("branford", 3); // Add location with name="branford" and score=3 to the system.

tracker.get(); // The sorted locations, from best to worst, are: branford, bradford.

// Note that branford precedes bradford due to its higher score (3 > 2).

// This is the 1st time get() is called, so return the best location: "branford".

tracker.add("alps", 2); // Add location with name="alps" and score=2 to the system.

tracker.get(); // Sorted locations: branford, alps, bradford.

// Note that alps precedes bradford even though they have the same score (2).

// This is because "alps" is lexicographically smaller than "bradford".

// Return the 2nd best location "alps", as it is the 2nd time get() is called.

tracker.add("orland", 2); // Add location with name="orland" and score=2 to the system.

tracker.get(); // Sorted locations: branford, alps, bradford, orland.

// Return "bradford", as it is the 3rd time get() is called.

tracker.add("orlando", 3); // Add location with name="orlando" and score=3 to the system.

tracker.get(); // Sorted locations: branford, orlando, alps, bradford, orland.

// Return "bradford".

tracker.add("alpine", 2); // Add location with name="alpine" and score=2 to the system.

tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland.

// Return "bradford".

tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland.

// Return "orland".

Constraints:

name consists of lowercase English letters, and is unique among all locations.
1 <= name.length <= 10
1 <= score <= 10⁵
At any time, the number of calls to get does not exceed the number of calls to add.
At most 4 * 10⁴ calls in total will be made to add and get.

Solution: TreeSet w/ Iterator

Use a treeset to store all the entries and use a iterator that points to the entry to return. When inserting a new entry into the tree, if it’s higher than the current element then let the iterator go backward one step.

Time complexity: add O(logn) / get O(1)

C++

// Author: Huahua

class SORTracker {

public:

SORTracker() {}

void add(string name, int score) {

if (*s.emplace(-score, name).first < *cit) --cit;

}

string get() {

return (cit++)->second;

}

private:

set<pair<int, string>> s;

// Note: cit points to begin(s) after first insertion.

set<pair<int, string>>::const_iterator cit = end(s);

};

花花酱 LeetCode 2007. Find Original Array From Doubled Array

By zxi on November 25, 2021

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].

Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.

Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.

Constraints:

1 <= changed.length <= 10⁵
0 <= changed[i] <= 10⁵

Solution 1: Multiset

Start from the smallest number x, erase one x * 2 from the set.

Time complexity: O(nlogn)
Space complexity: O(n)

C++/Multiset

// Author: Huahua

class Solution {

public:

vector<int> findOriginalArray(vector<int>& changed) {

if (changed.size() & 1) return {};

const int n = changed.size() / 2;

multiset<int> s(begin(changed), end(changed));

while (ans.size() != n) {

int o = *begin(s);

s.erase(begin(s));

ans.push_back(o);

auto it = s.find(o * 2);

if (it == end(s)) return {};

s.erase(it);

}

return ans;

}

};

Solution 2: Hashtable

Time complexity: O(max(nums) + n)
Space complexity: O(max(nums))

C++/Hashtable

// Author: Huahua

class Solution {

public:

vector<int> findOriginalArray(vector<int>& changed) {

if (changed.size() & 1) return {};

const int n = changed.size() / 2;

const int kMax = *max_element(begin(changed), end(changed));

vector<int> m(kMax + 1);

for (int x : changed) ++m[x];

if (m[0] & 1) return {};

vector<int> ans(m[0] / 2, 0);

for (int x = 1; ans.size() != n; ++x) {

if (x * 2 > kMax || m[x * 2] < m[x]) return {};

ans.insert(end(ans), m[x], x);

m[x * 2] -= m[x];

}

return ans;

}

};

花花酱 LeetCode 1845. Seat Reservation Manager

By zxi on May 1, 2021

Design a system that manages the reservation state of n seats that are numbered from 1 to n.

Implement the SeatManager class:

SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available.
int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.
void unreserve(int seatNumber) Unreserves the seat with the given seatNumber.

Example 1:

Input
["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"]
[[5], [], [], [2], [], [], [], [], [5]]
Output

[null, 1, 2, null, 2, 3, 4, 5, null]

Explanation SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats. seatManager.reserve(); // All seats are available, so return the lowest numbered seat, which is 1. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5]. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.reserve(); // The available seats are [3,4,5], so return the lowest of them, which is 3. seatManager.reserve(); // The available seats are [4,5], so return the lowest of them, which is 4. seatManager.reserve(); // The only available seat is seat 5, so return 5. seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5].

Constraints:

1 <= n <= 10⁵
1 <= seatNumber <= n
For each call to reserve, it is guaranteed that there will be at least one unreserved seat.
For each call to unreserve, it is guaranteed that seatNumber will be reserved.
At most 10⁵ calls in total will be made to reserve and unreserve.

Solution: TreeSet

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class SeatManager {

public:

SeatManager(int n) {

for (int i = 1; i <= n; ++i)

s_.insert(i);

}

int reserve() {

int seat = *begin(s_);

s_.erase(begin(s_));

return seat;

}

void unreserve(int seatNumber) {

s_.insert(seatNumber);

}

private:

set<int> s_;

};