Problem Description
You are given two 0-indexed integer arrays servers and tasks of lengths n and m respectively. servers[i] is the weight of the i-th server, and tasks[j] is the time needed to process the j-th task in seconds. Tasks are assigned to the servers using a task queue. Initially, all servers are free, and the queue is empty. At second j, the j-th task is inserted into the queue. As long as there are free servers and the queue is not empty, the task in the front of the queue will be assigned to a free server with the smallest weight, and in case of a tie, it is assigned to a free server with the smallest index. If there are no free servers and the queue is not empty, we wait until a server becomes free and immediately assign the next task. If multiple servers become free at the same time, then multiple tasks from the queue will be assigned in order of insertion following the weight and index priorities above. A server that is assigned task j at second t will be free again at second t + tasks[j]. Build an array ans of length m, where ans[j] is the index of the server the j-th task will be assigned to. Return the array ans.
Key Insights
- Use a min-heap (priority queue) to manage free servers based on weight and index.
- Use another min-heap to manage tasks waiting for server availability.
- Track when servers become free and assign tasks accordingly.
- Ensure tasks are processed in the order they arrive, respecting server availability.
Space and Time Complexity
Time Complexity: O((n + m) log n)
Space Complexity: O(n + m)
Solution
We will utilize two priority queues (min-heaps): one for the servers and one for the tasks. The server heap will prioritize servers based on their weight, and in case of ties, by their index. As tasks arrive, they will be added to the task queue. When a server becomes free, we will assign the next available task from the task queue to the server. This process will continue until all tasks are assigned.