- Define the priority key and whether the smallest or largest item should lead.
- Push each candidate when it becomes eligible.
- Discard stale entries when necessary and process the best live candidate.
Code notes
- 46 lines of C++ from the credited upstream file 1500.cpp.
- The implementation visibly relies on sequence storage, hash lookup, ordered lookup, work queue.
- 2 loop blocks detected.
Complexity
Count heap pushes and pops; each normally contributes a logarithmic factor in the heap size.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class FileSharing {2 public:3 FileSharing(int m) {}4 5 int join(vector<int> ownedChunks) {6 const int userId = getMinUserId();7 userToChunks[userId] = {ownedChunks.begin(), ownedChunks.end()};8 for (const int chunk : ownedChunks)9 chunkToUsers[chunk].insert(userId);10 return userId;11 }12 13 void leave(int userID) {14 for (const int chunk : userToChunks[userID]) {15 chunkToUsers[chunk].erase(userID);16 if (chunkToUsers[chunk].empty())17 chunkToUsers.erase(chunk);18 }19 userToChunks.erase(userID);20 availableUserIds.push(userID);21 }22 23 vector<int> request(int userID, int chunkID) {24 const auto it = chunkToUsers.find(chunkID);25 if (it == chunkToUsers.end())26 return {};27 vector<int> userIds{it->second.begin(), it->second.end()};28 userToChunks[userID].insert(chunkID);29 chunkToUsers[chunkID].insert(userID);30 return userIds;31 }32 33 private:34 unordered_map<int, set<int>> userToChunks;35 unordered_map<int, set<int>> chunkToUsers;36 priority_queue<int, vector<int>, greater<>> availableUserIds;37 38 int getMinUserId() {39 if (availableUserIds.empty())40 return userToChunks.size() + 1;41 const int minUserId = availableUserIds.top();42 availableUserIds.pop();43 return minUserId;44 }45};46