## Intuition The problem involves scheduling video recompression tasks on a set of servers. Each video can be processed by any available server, and if all servers are busy, the video must wait in a queue. The key insight is to manage the availability of servers efficiently, ensuring that each video is processed as soon as possible while respecting the order of their upload times. ## Approach 1. **Priority Queue for Server Management**: Use a priority queue (min-heap) to keep track of when each server becomes available. This allows us to efficiently determine the earliest available server. 2. **Process Each Video**: - For each video, check the earliest available server time. - If the server is available at or before the video's upload time, start processing immediately. - Otherwise, the video must wait until the earliest server becomes available. - Calculate the end time for the video as the start time plus the video duration. 3. **Update Server Availability**: After processing a video, update the server's next available time in the priority queue. 4. **Output the End Times**: For each video, output the time when it finishes processing. ## Complexity - **Time Complexity**: \(O(n \log k)\), where \(n\) is the number of videos and \(k\) is the number of servers. Each video operation involves a priority queue operation which is \(O(\log k)\). - **Space Complexity**: \(O(k)\) for storing server availability times in the priority queue. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; // Priority queue to keep track of when each server is available priority_queue, greater> serverAvailableTimes; // Initially, all servers are available at time 0 for (int i = 0; i < k; ++i) { serverAvailableTimes.push(0); } for (int i = 0; i < n; ++i) { long long si, mi; cin >> si >> mi; // Get the earliest available server time long long earliestServerTime = serverAvailableTimes.top(); serverAvailableTimes.pop(); // Determine when the video can start processing long long startProcessingTime = max(earliestServerTime, si); // Calculate when the video will finish processing long long endProcessingTime = startProcessingTime + mi; // Output the end processing time for this video cout << endProcessingTime << "\n"; // Update the server's next available time serverAvailableTimes.push(endProcessingTime); } return 0; } ``` This solution efficiently manages the scheduling of video recompression tasks using a priority queue to track server availability, ensuring that each video is processed as soon as possible while maintaining the order of uploads.

Statistics of Recompressing Videos

Problem Details