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] = [arrivali, leavingi], indicating the arrival and leaving times of the ith friend respectively, and an integer targetFriend. All arrival times are distinct.
Return the chair number that the friend numberedtargetFriendwill sit on.
Input: times =[[1,4],[2,3],[4,6]], targetFriend =1Output: 1Explanation:
- 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 return1.
Example 2:
1
2
3
4
5
6
7
8
9
10
Input: times =[[3,10],[1,5],[2,6]], targetFriend =0Output: 2Explanation:
- 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 return2.
Simulate the Chair Allocation: When a friend arrives, we need to find the smallest unoccupied chair. When they leave, that chair becomes available again.
Two Events:
Arrival events where a friend occupies the smallest available chair.
Leaving events where a chair is freed up.
Sorting: First, sort all events (both arrival and departure) by time. For events happening at the same time, handle departures before arrivals to ensure that any chair vacated is available immediately.
Data Structures:
Use a priority queue to keep track of the smallest available chairs.
Use a map (or hashmap) to associate each friend with their allocated chair.
Here is the approach:
Parse and sort the events.
Use a priority queue to manage chair allocation.
When processing arrivals, allocate the smallest available chair.
When processing departures, mark the chair as available again.
publicclassSolution {
publicintsmallestChair(int[][] times, int targetFriend) {
// List to hold all events List<int[]> events =new ArrayList<>();
// Create events for arrivals and departuresfor (int i = 0; i < times.length; i++) {
events.add(newint[]{times[i][0], 1, i}); // Arrival event events.add(newint[]{times[i][1], 0, i}); // Departure event }
// Sort events: first by time, then by type (departure before arrival if same time) events.sort((a, b) -> {
if (a[0]== b[0]) {
return Integer.compare(a[1], b[1]);
} else {
return Integer.compare(a[0], b[0]);
}
});
// Priority queue to track smallest available chairs PriorityQueue<Integer> availableChairs =new PriorityQueue<>();
for (int i = 0; i < times.length; i++) {
availableChairs.add(i);
}
// Map to store which chair a friend is sitting on Map<Integer, Integer> friendChairMap =new HashMap<>();
// Process each eventfor (int[] event : events) {
int time = event[0];
boolean isArrival = event[1]== 1;
int friendIdx = event[2];
if (isArrival) {
int chair = availableChairs.poll(); // Get the smallest available chair friendChairMap.put(friendIdx, chair); // Assign the chair to the friendif (friendIdx == targetFriend) {
return chair; // If it's the target friend, return the chair number }
} else {
availableChairs.add(friendChairMap.get(friendIdx)); // Free the chair }
}
return-1; // Should not reach here if inputs are valid }
}
classSolution:
defsmallestChair(self, times: List[List[int]], targetFriend: int) -> int:
# List to hold all events events = []
# Create events for arrivals and departuresfor i, (arrive, leave) in enumerate(times):
events.append((arrive, True, i)) # Arrival event events.append((leave, False, i)) # Departure event# Sort events: first by time, then by type (departure before arrival if same time) events.sort(key=lambda x: (x[0], not x[1]))
# Priority queue to track smallest available chairs available_chairs = list(range(len(times)))
heapq.heapify(available_chairs)
# Dictionary to store which chair a friend is sitting on friendChairMap = {}
# Process each eventfor time, is_arrival, friend_idx in events:
if is_arrival:
chair = heapq.heappop(available_chairs) # Get the smallest available chair friendChairMap[friend_idx] = chair # Assign the chair to the friendif friend_idx == targetFriend:
return chair # If it's the target friend, return the chair numberelse:
heapq.heappush(available_chairs, friendChairMap[friend_idx]) # Free the chair# Should not reach here if inputs are validreturn-1
We need to sort the times based on arrival time, which means we will loose the order of friends. So, before that, store the arrivalTime of targetFriend, since all the the arrival times are distinct this can be used to identify the targetFriend in sorted array.
Store all the available seats(one for each friend) in minHeap as available. Because we need to choose the min available chair number
Sort the times array based on arrival time.
Maintain another minHeap to store leavingTime and occupiedSeat.
loop through sorted array
remove all the friends from the heap whose leavingTime is less than or equal to current arraival time and add the occupied seats back to available heap.
if the current start is equal to targetStart return the min available seat.
else add the current leaving time and min available seat to heap.
classSolution {
publicintsmallestChair(int[][] times, int targetFriend) {
// Time at which targetFriend arrivesint targetStart = times[targetFriend][0];
// Sort the times array based on arrival times Arrays.sort(times, (a, b) -> a[0]- b[0]);
// Priority queue (min-heap) to store available chairs PriorityQueue<Integer> available =new PriorityQueue<>();
for (int i = 0; i < times.length; ++i) {
available.offer(i);
}
// Priority queue (min-heap) to store departure times and associated chairs PriorityQueue<int[]> pq =new PriorityQueue<>((a, b) -> a[0]- b[0]);
// Process each friend based on sorted arrival timesfor (int i = 0; i < times.length; ++i) {
// Free up chairs based on departure times before the current arrival timewhile (!pq.isEmpty() && pq.peek()[0]<= times[i][0]) {
available.offer(pq.poll()[1]);
}
// If we reach the target friend, break and return the smallest available chairif (times[i][0]== targetStart) {
break;
}
// Assign the smallest available chair to the current friend and add their departure time to the priority queue pq.offer(newint[]{times[i][1], available.poll()});
}
// Return the smallest available chair for the target friendreturn available.peek();
}
}
classSolution:
defsmallestChair(self, times: List[List[int]], targetFriend: int) -> int:
# Time at which targetFriend arrives targetStart = times[targetFriend][0]
# Sort the times array based on arrival times times.sort(key=lambda x: x[0])
# Priority queue (min-heap) to store available chairs available = list(range(len(times)))
heapq.heapify(available)
# Priority queue (min-heap) to store departure times and associated chairs pq = []
# Process each friend based on sorted arrival timesfor i in range(len(times)):
# Free up chairs based on departure times before the current arrival timewhile pq and pq[0][0] <= times[i][0]:
heapq.heappush(available, heapq.heappop(pq)[1])
# If we reach the target friend, break and return the smallest available chairif times[i][0] == targetStart:
break# Assign the smallest available chair to the current friend and add their departure time to the priority queue heapq.heappush(pq, (times[i][1], heapq.heappop(available)))
# Return the smallest available chair for the target friendreturn available[0]