Given an array arr[] representing the time required to complete n tasks. Each task has a specified time required for its completion. In each operation, one task is selected as the primary task and is executed for x units of time, while all other tasks are executed for y units of time, where y < x. A task is considered complete when it has been executed for at least the specified time required for its completion.

Find the minimum number of operations required to completely execute all tasks if the process runs optimally.

Examples:

Input: n = 5, arr[] = {3, 4, 1, 7, 6}, x = 4, and y = 2.
Output: 3
Explanation: Process goes like this

Iteration 1:

Choose task4 as the primary task

Update arr: {1, 2, -1, 3, 4}.

Task 3 is complete (1-2=-1).

Current state: {1, 2, -1, 3, 4}

Iteration 2:

Choose Task 4 again.

Update arr: {-1, 0, -1, -1, 2}.

Task 1, 2, and 4 are now complete (here 2-2=0, 3-4=-1, 4-2=2).

Current state: {-1, 0, -1, -1, 2}

Iteration 3:

Choose Task 5.

Update arr: {-, -, -, -, -2}.

Task 5 is complete.

Current state: {-, -, -, -, -2}

In total, three iterations are required to complete all jobs optimally.

Input: arr = {2, 3, 5}, x = 3, y = 1
Output:3
Explanation: The process goes like this

Iteration 1:

Choose task 3 as the major task

Update arr: {1, 2, 2}

Current state: {1, 2, 2}

Iteration 2:

Choose task 3 again.

Update arr: {0, 1, -1}.

Task 1 and 3 are now complete (here 1-1=0, 2-3=-1).

Current state: {0, 1, -1}

Iteration 3:

Choose task 2.

Update arr: {-1, -2, -1}.

task 2 is complete.

Current state: {-1, -2, -2}

In total, three iterations are required to complete all jobs optimally.

Approach: Follow the below steps to solve the problem

To solve this problem, we use priority queue. First, we repeatedly selecting the task with the maximum remaining execution time, executing it as the primary task, and updating the remaining times of all tasks. By using a priority queue (max heap), we efficiently keep track of the task with the maximum remaining time and update the execution times until all tasks are complete.

Step-by-step algorithm:

• Create a max heap (priority queue) from the given execution times.
• Initialize currentThreshold to 0 and numOps to 0.
• Repeat until the max heap is empty:
  • Pop the maximum execution time from the heap.
  • If the popped time is less than or equal to the currentThreshold, return the number of operations.
  • Add a new element to the heap with the value popped time – (x – y).
  • Update the currentThreshold by adding y.
  • Increment the number of operations.
• Return the final number of operations.

Below is the implementation of the approach:

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

int min_operations(int n, const vector<int>& times, int x, int y) {
    // Create a max heap (priority queue) from the given times
    priority_queue<int> maxHeap(times.begin(), times.end());
    
    // Initialize currentThreshold and numOps
    int currentThreshold = 0;
    int numOps = 0;
    
    // Process until the heap is empty
    while (!maxHeap.empty()) {
        // Pop the maximum time from the heap
        int maxTime = maxHeap.top();
        maxHeap.pop();
        
        // If the popped time is less than or equal to the current threshold, return the number of operations
        if (maxTime <= currentThreshold) {
            return numOps;
        }
        
        // Add the updated time to the heap
        maxHeap.push(maxTime - (x - y));
        
        // Update the current threshold by adding y
        currentThreshold += y;
        
        // Increment the number of operations
        numOps++;
    }
    
    // Return the total number of operations required
    return numOps;
}

int main() {
    // Test cases
    cout << min_operations(5, {3, 4, 1, 7, 6}, 4, 2) << endl;  // Output: 3
    cout << min_operations(3, {2, 3, 5}, 3, 1) << endl;  // Output: 3
    
    return 0;
}

3
3

Time Complexity: O(n * log(max(arr[]))), where n is the number of tasks and arr[] is the array storing the required time to complete a job.
Auxiliary Space: O(n) for the priority queue.