1942. The Number of the Smallest Unoccupied Chair #691
Answered
by
kovatz
mah-shamim
asked this question in
Q&A
-
|
Topics: There is a party where
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 Return the chair number that the friend numbered Example 1:
Example 2:
Example 3:
Example 4:
Example 5:
Example 6:
Example 7:
Example 8:
Constraints:
Hint:
|
Beta Was this translation helpful? Give feedback.
Answered by
kovatz
Oct 11, 2024
Replies: 1 comment 2 replies
-
|
We need to simulate the arrival and departure of friends at a party and manage the assignment of the smallest available chairs. Here's the step-by-step approach: Approach:
Let's implement this solution in PHP: 1942. The Number of the Smallest Unoccupied Chair <?php
/**
* @param Integer[][] $times
* @param Integer $targetFriend
* @return Integer
*/
function smallestChair($times, $targetFriend) {
$nextUnsatChair = 0;
$emptyChairs = new SplMinHeap(); // Min heap for empty chairs
$occupied = new SplMinHeap(); // Min heap for occupied chairs
// Append the index to each time entry
foreach ($times as $i => $time) {
$times[$i][] = $i; // Add index to the end of each time entry
}
// Sort times based on arrival time
usort($times, function($a, $b) {
return $a[0] - $b[0];
});
foreach ($times as $time) {
$arrival = $time[0];
$leaving = $time[1];
$i = $time[2];
// Free chairs that have become available
while (!$occupied->isEmpty() && $occupied->top()[0] <= $arrival) {
$emptyChairs->insert($occupied->top()[1]);
$occupied->extract(); // Remove the top element
}
// Check if this is the target friend
if ($i == $targetFriend) {
return $emptyChairs->isEmpty() ? $nextUnsatChair : $emptyChairs->top();
}
// Allocate chair
if ($emptyChairs->isEmpty()) {
$occupied->insert([$leaving, $nextUnsatChair++]);
} else {
$occupied->insert([$leaving, $emptyChairs->top()]);
$emptyChairs->extract(); // Remove the used chair
}
}
return -1; // This should never happen
}
// Example usage:
$cost1 = [[15, 96], [36, 2]];
$cost2 = [[1, 3, 5], [4, 1, 1], [1, 5, 3]];
$cost3 = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]];
// Example usage:
$times1 = [[1, 4], [2, 3], [4, 6]];
$targetFriend1 = 1;
echo smallestChair($times1, $targetFriend1); // Output: 1
$times2 = [[3, 10], [1, 5], [2, 6]];
$targetFriend2 = 0;
echo smallestChair($times2, $targetFriend2); // Output: 2
?>Explanation:
Complexity:
This solution efficiently handles the assignment of chairs, ensuring that each friend gets the smallest available chair, and accurately tracks when chairs become available again. |
Beta Was this translation helpful? Give feedback.
2 replies
-
|
Thanks to solve the "Number of the Smallest Unoccupied Chair" problem |
Beta Was this translation helpful? Give feedback.
-
|
Thanks |
Beta Was this translation helpful? Give feedback.
Answer selected by
mah-shamim
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
We need to simulate the arrival and departure of friends at a party and manage the assignment of the smallest available chairs. Here's the step-by-step approach:
Approach:
Sort by Arrival Times:
timesarray based on the arrival time.Use Priority Queues (Min-Heaps):
availableChairs).occupiedChairs).Iterate Through Sorted Times: