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.
1import heapq
2
3def smallestChair(times, targetFriend):
4 events = []
5 for i, (arr, leave) in enumerate(times):
6 events.append((arr, i, 'arrive'))
7 events.append((leave, i, 'leave'))
8 events.sort()
9
10 available_chairs = [] # Min-heap for available chair numbers
11 occupied_map = {} # Maps friends to chairs
12 current_chair = 0
13
14 for time, friend, event_type in events:
15 if event_type == 'arrive':
16 if not available_chairs:
17 chair = current_chair
18 current_chair += 1
19 else:
20 chair = heapq.heappop(available_chairs)
21
22 occupied_map[friend] = chair
23
24 if friend == targetFriend:
25 return chair
26 else: # event_type == 'leave'
27 heapq.heappush(available_chairs, occupied_map[friend])
28This Python function uses two main structures: a list of events that are sorted by time, and a min-heap to keep track of the smallest available chairs. We iterate through each event, either assigning an available chair to an arriving friend or freeing up a chair when a friend leaves. This method works because the heap operations are logarithmic, keeping the solution efficient.
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.