Sponsored
Sponsored
The problem can be efficiently solved by using a min-heap (priority queue) to keep track of the smallest available chair. When a friend arrives, we assign them the smallest chair, and when they leave, their chair is added back to the pool of available chairs. This ensures that friends always get the smallest possible available chair.
We start by sorting all events by time. As we process each event, we use the heap to efficiently manage the available chairs.
Time Complexity: O(n log n), where n is the number of friends (and thus events). This is due to sorting the events and using heap operations.
Space Complexity: O(n) for storing event data and the heap.
1function smallestChair(times, targetFriend) {
2 let events = [];
3 times.forEach(([arrival, leave], index) => {
4 events.push({ time: arrival, index, type: 'arrive' });
5 events.push({ time: leave, index, type: 'leave' });
6 });
7 events.sort((a, b) => a.time - b.time || (a.type === 'leave' ? -1 : 1));
8
9 let availableChairs = new MinPriorityQueue();
10 let occupiedChairs = new Map();
11 let currentChair = 0;
12
13 for (const { time, index, type } of events) {
14 if (type === 'arrive') {
15 let chair = availableChairs.isEmpty() ? currentChair++ : availableChairs.dequeue().element;
16 occupiedChairs.set(index, chair);
17
18 if (index === targetFriend) {
19 return chair;
20 }
21 } else {
22 availableChairs.enqueue(occupiedChairs.get(index));
23 }
24 }
25}This JavaScript solution utilizes a MinPriorityQueue for handling available chairs similarly to a min-heap. Events are sorted by time, and each arrival and leave is processed in order, updating the state of available and occupied chairs.
This approach involves handling chair availability using a sorted list (or equivalent structure) to manage the sequence of chairs efficiently. We simulate arrival and departure events by updating the list and assigning chairs accordingly. While slightly less efficient than a heap in handling dynamic minimum queries, it offers an alternative perspective by focusing on set management operations.
Time Complexity: O(n log n) primarily due to sorting events and set operations.
Space Complexity: O(n) for storing chair assignments and event data.
1#include <vector>
2#include <algorithm>
3#include <set>
4using namespace std;
5
int smallestChair(vector<vector<int>>& times, int targetFriend) {
vector<pair<int, int>> events;
for (int i = 0; i < times.size(); ++i) {
events.emplace_back(times[i][0], i);
events.emplace_back(times[i][1], -i);
}
sort(events.begin(), events.end());
set<int> available_chairs;
vector<int> friend_to_chair(times.size(), -1);
int next_chair = 0;
for (const auto& event : events) {
int time = event.first;
int index = event.second;
if (index >= 0) { // Arrival event
int chairNumber;
if (!available_chairs.empty()) {
chairNumber = *available_chairs.begin();
available_chairs.erase(available_chairs.begin());
} else {
chairNumber = next_chair++;
}
friend_to_chair[index] = chairNumber;
if (index == targetFriend)
return chairNumber;
} else { // Departure event
int leavingFriend = -index;
available_chairs.insert(friend_to_chair[leavingFriend]);
}
}
return -1;
}This C++ solution uses a sorted set (implemented typically with Red-Black Trees in the STL set) to track available chairs and assigns them to arriving friends. When a friend arrives, we select the smallest available chair, either from the set or by incrementing. When a friend leaves, we return the chair to the set.