- Data Structures and Algorithms
Preface
- Preface
Online Judges
- Why, What and How?
- Popular Online Platforms
- Tearing Down a Problem
Time & Space Complexity
- Inroduction to Time Complexity
- Introduction to Space Complexity
- Different Notations in Time Complexity
- Comparing Different Time Complexities
- How to Calculate Time Complexity?
- Quiz: Time Complexity
Control Flow Practice
- if-else and else-if ladder Practice
- Loops Practice 1
- Loops Practice 2
- Loops Practice 3
- Loops Practice 4
- Square Star and Rhombus Star Patterns
- Triangle Star Patterns
- Pyramid Star Patterns
- Miscellaneous Star Patterns
- Number Patterns 1
- Number Patterns 2
- Triangular Number Patterns 1
- Triangular Number Patterns 2
- Triangular Number Patterns 3
- Switch Statement Practice
Array Basics
- Print Each Element and its Index in an Array Solution in C++/Java/Python/JS
- Print Array in Reverse Order Solution in C++/Java/Python/JS
- Print Alternate Elements of an Array Solution in C++/Java/Python/JS
- Create Duplicate of an Array
- Separate Odd and Even Elements of an Array Solution in C++/Java/Python/JS
- Find Sum and Product of All the Elements in an Array Solution in C++/Java/Python/JS
- Find Number of Times Target Appear in Array
- Check if an Array is Sorted
- Find Count of Unique and Duplicate Elements in an Array Solution in C++/Java/Python/JS
- Sum of Pair Equal to Target in Array
- Sum of Triplet Equal to Target in Array
- Find Maximum Element in Array
- Find Minimum Element in Array
- Find 2nd Maximum in Array
- Find 2nd Minimum in Array
- Insertion at Xth Position Solution in C++/Java/Python/JS
- Deletion at Xth Position
String Basics
- Coming Soon.
Matrix Basics
- Coming Soon..
- 2D-Arrays I
- 2D- Arrays II
- 2D-Arrays III
- 2D-Arrays IV
- 2D-Arrays V
Math Basics
- Introduction to Basic Math
- Find the Sum of Digits of a Number
- Reverse a Given Number
- Check if a Number is a Palindrome
- Check if a Number is an Armstrong Number
- Count the Occurrences of Digit '1' in All Numbers from 1 to n Solution In C++/Java/Python/JS
- Generate Fibonacci Numbers up to a Given Limit Solution in C++/Java/Python/JS
- Calculate the Factorial of a Number
- Find the Number of Trailing Zeroes in the Factorial of a Given Number n
- Calculate the LCM and GCD of Two Numbers Solution In C++/Java/Python/JS
- Check if a number is prime without using the Sieve of Eratosthenes Solution In C++/Java/Python/JS
- Check if two numbers are co-prime or not Solution In C++/Java/Python/JS
- Find All Divisors of a Given Number
- Perform Modulo Operations
- Check Divisibility Rules for Numbers from 1 to 20
- How to Find Ceil and Floor Solution In C++/Java/Python/JS
- How to Find nPr and nCr Solution In C++/Java/Python/JS
- Implement Power Function (pow(x,n)) Solution in C++/Java/Python/JS
- Check if an Integer is a Power of 2/3/4/5... Solution In C++/Java/Python/JS
- Find the Mean/Median/Mode of the Given Array Solution In C++/Java/Python/JS
- Find the AP/GP/HP Solution In C++/Java/Python/JS
- Logarithm basics for DSA Solution In C++/Java/Python/JS
- Number System
Recursion Basics
- Introduction to Recursion - Understand Recursion by Examples
- Getting a Hang of Recursion
- Most Asked Recursion Practice Problems with Solutions
- Fast Exponentiation Algorithm: Efficient Power Calculation Explained
- Find Whether a Given Integer is a Power of 3: Power of Three
- Recursion: Time & Space Complexity Analysis - 1
- Recursion: Time & Space Complexity Analysis - 2
- Time Complexity Analysis Using Recurrence Relations
- Coming Soon..
Sorting
- Bubble Sort Algorithm
- Selection Sort Algorithm
- Insertion Sort Algorithm
- First Missing Positive Solution In C++/Java/Python/Javascript
- Merge Sort
- Quick Sort
- Counting Sort
- Comparator Sort
- +5 Problems on Comparator Sort | Code C++/Python/Java
- Largest Number
- Sort the Jumbled Numbers
- Custom Sort String Solution In C++/Java/Python/Javascript
- Rank Teams by Votes
Two Pointer
- Reverse String
- Merge Strings Alternately
- Minimum Length of String After Deleting Similar Ends
- Merge Two 2D Arrays by Summing Values
- Container with Most Water
- String Compression
- Reverse Prefix of Word
- Separate Black and White Balls
- Merge Sorted Array
- Watering Plants II
- Two Sum Solution In C++/Java/Python/JS
- Sort Array By Parity
- Rotate Array
- Sentence Similarity III
- Next Greater Element III
- Next Permutation
- Move Pieces to Obtain a String
- Partition Array According to Given Pivot Solution Code in C++/Python/Java/JS
- Lexicographically Smallest Palindrome Solution Code in C++/Java/Python/JavaScript
- Shortest Distance to a Character Solution Code in C++/Java/Python/JavaScript
- Reverse Vowels of a String Solution In C++/Java/Python/JS
- Sort Array By Parity II Solution In C++/Java/Python/JS
- 3 Sum Solution In C++/Java/Python/JS
- 3Sum Closest Solution In C++/Java/Python/JS
- Sort Colours Solution In C++/Java/Python/JS
- Rearrange Array Elements by Sign
- Remove Element Solution In C++/Java/Python/JS
- Apply Operations to an Array Solution In C++/Java/Python/JS
- Find All K-Distant Indices in an Array Solution In C++/Java/Python/JS
- 4Sum Solution In C++/Java/Python/JS
- Reverse Words in a String Solution In C++/Java/Python/JS
- Reverse Words in a String III Solution In C++/Java/Python/JS
- Largest Merge Of Two Strings Solution In C++/Java/Python/JS
- Make String a Subsequence Using Cyclic Increments Solution In C++/Java/Python/JS
Prefix Sum
- Range Sum Query - Immutable
- Subarray Sum Equals K
- Minimum Penalty for a Shop
- Product of Array Except Self
- Sum of Absolute Differences in a Sorted Array
- Find Good Days to Rob the Bank
- Subarray Sums Divisible by K
- Make Sum Divisible by P
- Removing Minimum Number of Magic Beans
- Product of the Last K Numbers
- Count Number of Bad Pairs Solution In C++/Java/Python/JS
- Continuous Subarray Sum
- Count of Interesting Subarrays
- Movement of Robots
- Find All Good Indices
- Count Number of Nice Subarrays Solution In C++/Python/java/JS
- Maximum Population Year
- Points That Intersect With Cars
- Pongal Bunk
- Car Pooling
- Shifting Letters II
- My Calendar II
- Left and Right Sum Differences
- Count Vowel Strings in Ranges Solution In C++/Java/Python/JS
- Minimum Cost to Make Array Equal Solution In C++/Java/Python/JS
- Number of Flowers in Full Bloom Solution In C++/Java/Python/JS
- Rectangle Area II Solution In C++/Java/Python/JS
- Perfect Rectangle Solution In C++/Java/Python/JS
Matrix
- Convert 1D Array Into 2D Array
- Modify the Matrix
- Set Matrix Zeroes
- Sort the Matrix Diagonally Solution In C++/Python/java/JS
- Minimum Operations to Write the Letter Y on a Grid Solution In C++/Python/java/JS
- Shift 2D Grid Solution in C++/Java/Python/JS
- Matrix Similarity After Cyclic Shifts Solution In C++/Python/java/JS
- Transpose Matrix Solution In C++/Python/java/JS
- Rotate Image
- Rotating the Box Solution In C++/Python/java/JS
- Cyclically Rotating a Grid Solution In C++/Python/java/JS
- Game of Life Solution In C++/Python/java/JS
- Matrix Cells in Distance Order Solution In C++/Python/java/JS
- Find Valid Matrix Given Row and Column Sums Solution In C++/Python/java/JS
- Check if Matrix is X-Matrix
- Queens That Can Attack The King
- Max Increase to Keep City Skyline Solution In C++/Python/java/JS
- Make a Square with the Same Color Solution In C++/Python/java/JS
- Subrectangle Queries Solution In C++/Python/java/JS
- Find the Minimum Area to Cover All Ones I Solution In C++/Python/java/JS
- Find the Minimum Area to Cover All Ones II Solution In C++/Python/java/JS
- Valid Sudoku Solution In C++/Python/java/JS
- Check if Move is Legal Solution In C++/Python/java/JS
- Valid Tic-Tac-Toe State Solution In C++/Python/java/JS
- Number of Laser Beams in a Bank Solution In C++/Python/java/JS
- Where Will the Ball Fall Solution In C++/Python/java/JS
- Image Overlap Solution In C++/Python/java/JS
- Minimum Operations to Make a Uni-Value Grid Solution In C++/Python/java/JS
- Row with Maximum ones
- Richest Customer Wealth
- Lucky Numbers in a Matrix
- Equal Row and Column Pairs Solution In C++/Python/java/JS
- Difference Between Ones and Zeros in Row and Column Solution In C++/Python/java/JS
- Matrix Diagonal Sum
- Prime In Diagonal
- Diagonal Traverse Solution In C++/Python/java/JS
- Matrix Block Sum Solution In C++/Python/java/JS
- Largest Local Values in a Matrix
- Maximum Sum of an Hourglass Solution In C++/Python/java/JS
- Maximum Matrix Sum
- Find the Grid of Region Average Solution In C++/Python/java/JS
- Spiral Matrix
- Spiral Matrix II
Hashing
- Subarray Sum Equals K
- First Missing Positive Solution In C++/Java/Python/Javascript
- Isomorphic Strings Solution In C++/Python/Java/Javascript
- Find Common Elements Between Two Arrays Solution In C++/Java/Python/Javascript
- Majority Element Solution In C++/Python/Java/Javascript
- Majority Element II Solution In C++/Python/Java/Javascript
- Substrings of Size Three with Distinct Characters Solution In C++/Python/Java/Javascript
- Contains Duplicate Solution In C++/Python/Java/Javascript
- Subarray Sums Divisible by K
- Make Sum Divisible by P
- Count Number of Bad Pairs Solution In C++/Java/Python/JS
- Continuous Subarray Sum
- Count of Interesting Subarrays
- Count Number of Nice Subarrays Solution In C++/Python/java/JS
- Sum of Unique Elements Solution In C++/Python/Java/Javascript
- Optimal Partition of String Solution In C++/Python/Java/Javascript
- Groups of Special-Equivalent Strings Solution In C++/Python/Java/Javascript
- Word Subsets Solution In C++/Python/Java/Javascript
- Find the Maximum Number of Elements in Subset Solution In C++/Python/Java/Javascript
- People Whose List of Favorite Companies is Not a Subset of Another List Solution In C++/Python/Java/Javascript
- Custom Sort String Solution In C++/Java/Python/Javascript
- Count the Number of Good Partitions Solution In C++/Python/Java/Javascript
- Count Beautiful Substrings II Solution In C++/Java/Python/JS
- Finding the Users Active Minutes Solution In C++/Java/Python/Javascript
- Convert an Array Into a 2D Array With Conditions Solution In C++/Java/Python/Javascript
- Group the People Given the Group Size They Belong To Solution In C++/Java/Python/Javascript
- Evaluate the Bracket Pairs of a String Solution In C++/Java/Python/Javascript
- Count the Number of Special Characters II Solution In C++/Java/Python/Javascript
- Reconstruct Original Digits from English Solution In C++/Java/Python/Javascript
- Integer to Roman Solution In C++/Java/Python/Javascript
- Find Words That Can Be Formed by Characters Solution In C++/Java/Python/Javascript
- Replace Elements in an Array Solution In C++/Java/Python/Javascript
- Count Artifacts That Can Be Extracted Solution In C++/Java/Python/Javascript
- 4Sum II Solution In C++/Java/Python/Javascript
- Split the Array to Make Coprime Products Solution In C++/Java/Python/Javascript
- Tuple with Same Product Solution In C++/Java/Python/Javascript
- Restore the Array From Adjacent Pairs Solution In C++/Java/Python/Javascript
- Can Convert String in K Moves Solution In C++/Java/Python/Javascript
- Minimum Number of Operations to Make Word K-Periodic Solution In C++/Java/Python/Javascript
- Sort Characters By Frequency Solution In C++/Java/Python/Javascript
- Brick Wall Solution In C++/Java/Python/JS
- Pairs of Songs With Total Durations Divisible by 60 Solution In C++/Java/Python/JS
- Alphabet Board Path Solution In C++/Java/Python/JS
- Vowel Spellchecker Solution In C++/Java/Python/JS
- Card Flipping Game Solution In C++/Java/Python/JS
- Maximum Size of a Set After Removals Solution In C++/Java/Python/JS
- Minimum Seconds to Equalize a Circular Array Solution In C++/Java/Python/JS
Sliding Window
- Maximum Number of Occurrences of a Substring
- Longest Substring Without Repeating Characters
- Count the Number of Substrings With Dominant Ones
- Minimum Size Subarray Sum
- Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
- Longest Repeating Character Replacement
- Max Consecutive Ones III Solution In C++/Python/Java/JS
- Substrings of Size Three with Distinct Characters Solution In C++/Python/Java/Javascript
- Minimum Window Substring
- Substring with Concatenation of All Words
- Max Value of Equation Solution In C++/Python/Java/JS
- Find All Anagrams in a String Solution In C++/Java/Python/JS
- Sliding Subarray Beauty Solution In C++/Java/Python/JS
- Maximum Points You Can Obtain from Cards Solution In C++/Java/Python/JS
- Fruit Into Baskets Solution In C++/Java/Python/JS
- Grumpy Bookstore Owner Solution In C++/Java/Python/JS
Linked List
Stack
- Next Greater Element I
- Merge Intervals
- Insert Intervals
- Valid Parentheses
- Asteroid Collision
- Minimum Add to Make Parentheses Valid
- Minimum Remove to Make Valid Parentheses
- Coming Soon..
- Maximum Nesting Depth of the Parentheses
- Reverse Substrings Between Each Pair of Parentheses
- Remove Outermost Parentheses
- Check if a Parentheses String Can Be Valid
- Min Stack
- Maximum Frequency Stack
- Score of Parentheses
- Dinner Plate Stacks
- Simplify Path Solution In C++/Python/Java/JS
Queue
- Coming Soon..
Binary Search
- Coming Soon..
- Binary Search Algorithm Solution: Iterative & Recursive Ways
- Sqrt(x) LeetCode Solution | Approaches in C++/Java/Python/JS
- Find Peak Element LeetCode Solution | Code in C++/Java/Python/JS
- Find Minimum in Rotated Sorted Array Solution In C++/Java/Python/JS
- Find Peak Index in a Mountain Array Solution | Code In C++/Java/Python/JS
- Search in Rotated Sorted Array Leetcode Solution | Code In C++/Python/Java/JS
- Maximum Value at a Given Index in a Bounded Array Solution in C++/Java/Python/JS
- Most Profit Assigning Work Leetcode Solution
- Maximum Candies Allocated to K Children Solution
- Aggressive Cows Leetcode Solution
- Maximum Side Length of a Square with Sum Less than or Equal to Threshold
- Minimum Speed to Arrive on Time Solution in C++/Java/Python/JS
- Minimum Time to Repair Cars Solution in C++/Java/Python/JS
- Maximum Number of Removable Characters Solution in C++/Java/Python/JS
- Heaters Leetcode Solution in C++/Java/Python/JS
- Earliest Second to Mark Indices I Solution in C++/Java/Python/JS
- Maximum White Tiles Covered by a Carpet Solution in C++/Java/Python/JS
- Minimum Absolute Difference Between Elements with Constraint Solution in C++/Java/Python/JS
- Sell Diminishing-Valued Colored Balls Solution in C++/Java/Python/JS
- Ugly Number III Solution In C++/Python/Java/JS
- Minimize the Maximum of Two Arrays Solution in C++/Java/Python/JS
- Find a Peak Element II Solution In C++/Java/Python/JS
- Guess Number Higher or Lower Solution In C++/Java/Python/JS
- H-Index II Solution In C++/Java/Python/JS
- Find First and Last Position of Element in Sorted Array Solution | Code in C++/Java/Python/JS
- Special Array with X Elements Greater Than or Equal X Solution In C++/Java/Python/JS
- Longest Subsequence with Limited Sum Solution in C++/Java/Python/JS
- Arranging Coins Solution In C++/Java/Python/JS
- Find Smallest Letter Greater Than Target Solution in C++/Java/Python/JS
- First Bad Version Solution in C++/Java/Python/JS
- Find the Distance Value Between Two Arrays Solution In C++/Java/Python/JS
- Search Insert Position Solution In C++/Java/Python/JS
- Find Target Indices After Sorting Array Solution In C++/Java/Python/JS
- Online Election Solution In C++/Java/Python/JS
- Most Beautiful Item for Each Query Solution In C++/Java/Python/JS
- Kth Missing Positive Number Solution In C++/Java/Python/JS
- Single Element in a Sorted Array Solution In C++/Java/Python/JS
- Minimum Common Value Solution In C++/Java/Python/JS
- Find the Duplicate Number Solution In C++/Java/Python/JS
- Find Minimum in Rotated Sorted Array II Solution In C++/Java/Python/JS
- Find in Mountain Array Solution In C++/Java/Python/JS
- Capacity To Ship Packages Within D Days Solution In C++/Java/Python/JS
- Koko Eating Bananas Solution In C++/Java/Python/JS
- Find the Smallest Divisor Given a Threshold Solution In C++/Java/Python/JS
- Minimum Number of Days to Make m Bouquets Solution In C++/Java/Python/JS
- Split Array Largest Sum Solution In C++/Java/Python/JS
- Maximum Running Time of N Computers Solution In C++/Java/Python/JS
- Maximum Number of Robots Within Budget Solution In C++/Java/Python/JS
Bit Manipulation
- Coming Soon..
Recursion and Backtracking
- Coming Soon..
Trees
- Coming Soon..
Heaps
- Max Value of Equation Solution In C++/Python/Java/JS
- Sort Characters By Frequency Solution In C++/Java/Python/Javascript
- Reduce Array Size to The Half Solution In C++/Java/Python/Javascript
- Longest Happy String Solution In C++/Java/Python/Javascript
- Reorganize String Solution In C++/Java/Python/Javascript
- Maximum Average Pass Ratio Solution In C++/Java/Python/Javascript
- Single Threaded CPU Problem Solution In C++/Java/Python/Javascript
- Most Popular Video Creator Problem Solution In C++/Java/Python/Javascript
- Total Cost to Hire K Workers Problem Solution In C++/Java/Python/Javascript
- Most Frequent IDs Problem Solution In C++/Java/Python/Javascript
- Process Tasks Using Servers Solution In C++/Java/Python/Javascript
- Maximum Number of Eaten Apples Problem Solution In C++/Java/Python/Javascript
- Maximum Number of Events That Can Be Attended Solution In C++/Java/Python/Javascript
- Minimum Operations to Exceed Threshold Value II Solution In C++/Java/Python/Javascript
- Maximum Performance of a Team Solution In C++/Python/Java/JS
- Maximum Elegance of a K-Length Subsequence Solution In C++/Python/Java/JS
- Maximum Subsequence Score Solution In C++/Python/Java/JS
Tries
- Coming Soon..
Greedy
- Maximum 69 Number
- Maximum Sum With Exactly K Elements
- Minimum Time to Type Word Using Special Typewriter
- Minimum Operations to Make the Array Increasing
- Minimum Number of Operations to Convert Time
- Lemonade Change
- Assign Cookies
- Minimum Cost to Move Chips to the Same Position Solution in C++/Java/Python/JS
- Jump Game Solution In C++/Java/Python/JS
- Jump Game II Solution In C++/Java/Python/JS
- Wiggle Subsequence Solution In C++/Java/Python/JS
- Advantage Shuffle Solution In C++/Java/Python/JS
- Minimum Score by Changing Two Elements Solution In C++/Java/Python/JS
- Minimum Operations to Make Array Equal II Solution In C++/Java/Python/JS
- Maximum Bags With Full Capacity of Rocks Solution In C++/Java/Python/JS
- Minimize Maximum of Array Solution In C++/Java/Python/JS
Dynamic Programming
Graphs
- Coming Soon..
String Matching Algorithms
Combinatorics
Geometry
Game Theory
Advanced Algorithm

Heaps

Process Tasks Using Servers Solution In C++/Java/Python/Javascript

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 (starting with the 0^th task being inserted at second 0). 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.

Example

Input: servers = [3,3,2], tasks = [1,2,3,2,1,2]
Output: [2,2,0,2,1,2]
Explanation: Events in chronological order go as follows:
- At second 0, task 0 is added and processed using server 2 until second 1.
- At second 1, server 2 becomes free. Task 1 is added and processed using server 2 until second 3.
- At second 2, task 2 is added and processed using server 0 until second 5.
- At second 3, server 2 becomes free. Task 3 is added and processed using server 2 until second 5.
- At second 4, task 4 is added and processed using server 1 until second 5.
- At second 5, all servers become free. Task 5 is added and processed using server 2 until second 7.

Input: servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
Output: [1,4,1,4,1,3,2]
Explanation: Events in chronological order go as follows:
- At second 0, task 0 is added and processed using server 1 until second 2.
- At second 1, task 1 is added and processed using server 4 until second 2.
- At second 2, servers 1 and 4 become free. Task 2 is added and processed using server 1 until second 4.
- At second 3, task 3 is added and processed using server 4 until second 7.
- At second 4, server 1 becomes free. Task 4 is added and processed using server 1 until second 9.
- At second 5, task 5 is added and processed using server 3 until second 7.
- At second 6, task 6 is added and processed using server 2 until second 7.

Constraints:

servers.length == n
tasks.length == m
1 <= n, m <= 2 * 10⁵
1 <= servers[i], tasks[j] <= 2 * 10⁵

💡

Try it Yourself

The problem involves assigning incoming tasks to a set of servers that each have a specific weight and index. Every second, a new task is added to a queue and is immediately assigned to the free server with the smallest weight (using the smallest index to break ties). If no servers are free, the task waits until one becomes available. Each server takes a given amount of time to complete a task, and the assignment order must be tracked in an output array.

Optimal Approach

Intuition

Imagine you're managing a busy restaurant kitchen with several cooks, each with their own performance rating. Each cook's rating is similar to a server's weight, where a lower rating indicates a more efficient cook. As customers arrive—each representing a new task—they need to be served immediately by the available cook who is the best fit, meaning the one with the lowest performance rating (and the lowest index in case of a tie). If all cooks are busy, the customer waits until one of them finishes their current order.

To manage this system efficiently, it's essential to track both available and busy cooks. For available cooks, a structure like a min-heap allows you to quickly identify the best cook at any moment. At the same time, you need another mechanism to monitor busy cooks, keeping track of when they will complete their tasks so that they can be marked as free. This dual-tracking ensures that every incoming order is processed as soon as a cook is ready.

Simulating the passage of time is another critical element. Each second, a new order is added to the queue, and you continuously check if any cook has finished their current task. When a cook becomes free, the system immediately assigns the next waiting order based on the established priorities. This step-by-step process mirrors the flow of a real kitchen, ensuring that orders are managed efficiently without any unnecessary delays.

How does task assignment work when servers are free or busy?

When a task arrives, if there is a free server, it is assigned immediately to the optimal server based on the smallest weight and then by index. If all servers are busy at that moment, the task is put into a waiting queue. As soon as one or more servers finish their tasks, the waiting tasks are assigned in order, ensuring that the next task always goes to the best available server.

Why do we need special data structures like priority queues (min-heaps) in this problem?

Priority queues are essential because they help efficiently determine which server should handle the next task. One min-heap keeps track of free servers so you can quickly choose the one with the smallest weight (and index). Another min-heap can manage busy servers by keeping track of when each will be free. This allows the simulation to update server availability in real time and assign waiting tasks as soon as possible.

Approach

Step 1: Input Parsing

Read the two input arrays: one for servers and one for tasks.
Each element in the servers array represents the weight (or efficiency) of a server.
Each element in the tasks array represents the processing time required for that task.

Step 2: Data Structures Initialization

Initialize a min-heap for free servers. This heap will store servers using a tuple (weight, index) to quickly select the best available server.
Initialize a second min-heap for busy servers. This heap will track servers currently processing tasks by storing tuples that include the finish time, weight, and index.

Step 3: Time Simulation Start

Begin a simulation that iterates over time, where each second corresponds to the arrival of a new task from the tasks array.
At every second, the task that arrives is either immediately processed or placed in a waiting queue if no server is free.

Step 4: Check for Free Servers

At each time step, check the busy servers min-heap to see if any server’s finish time is less than or equal to the current time.
If a server has finished processing its task, remove it from the busy heap and add it back to the free servers heap.

Step 5: Task Assignment

When a task is waiting, check if there is at least one free server available in the free servers heap.
Assign the task to the optimal server (the one with the smallest weight and, in the case of a tie, the smallest index).
Calculate the finish time for the assigned server by adding the task’s processing time to the current time.
Add the server along with its new finish time back to the busy servers heap.

Step 6: Handling Unavailable Servers

If no servers are free when a task arrives, wait until the next server becomes available.
As soon as a server becomes free, immediately assign the waiting task to it, following the same assignment process.

Step 7: Continue Until Completion

Repeat the process of checking for free servers and assigning tasks until every task in the tasks array has been processed.
For each task assignment, record the index of the server that processed the task.

Step 8: Return the Result

After processing all tasks, compile the recorded server indices into an answer array.
Return this array, where each element corresponds to the server that handled the respective task.

Dry Run

Example with servers = [3, 3, 2] and
tasks = [1, 2, 3, 2, 1, 2]

Step 1: Input Parsing

Servers: [3, 3, 2] (weights for server 0, server 1, and server 2)
Tasks: [1, 2, 3, 2, 1, 2] (processing times for tasks 0 through 5)

Step 2: Data Structures Initialization

Free Servers Min-Heap is initialized with:
- (2, 2) from server 2
- (3, 0) from server 0
- (3, 1) from server 1
Busy Servers Min-Heap is empty initially.

Step 3: Time Simulation Start

At Time 0:

Task 0 arrives with processing time 1.
Free servers available: (2, 2), (3, 0), (3, 1)
Select the optimal server: (2, 2) (server 2 is the best since it has the smallest weight).
Calculate finish time: 0 + 1 = 1.
Remove (2, 2) from free servers and add (1, 2, 2) to busy servers (finish time, weight, index).
Record assignment: Task 0 → Server 2.

At Time 1:

Task 1 arrives with processing time 2.
Check busy servers: (1, 2, 2) has finish time 1 which is ≤ current time, so pop it.
Add server 2 back to free servers as (2, 2).
Free servers now: (2, 2), (3, 0), (3, 1)
Select the optimal server: (2, 2) (server 2 again).
Calculate finish time: 1 + 2 = 3.
Remove (2, 2) from free servers and add (3, 2, 2) to busy servers.
Record assignment: Task 1 → Server 2.

At Time 2:

Task 2 arrives with processing time 3.
Check busy servers: Top is (3, 2, 2) with finish time 3 (not yet free as 3 > 2).
Free servers available: (3, 0) and (3, 1).
Select the optimal server: (3, 0) (server 0, since index 0 is less than index 1 when weights are equal).
Calculate finish time: 2 + 3 = 5.
Remove (3, 0) from free servers and add (5, 3, 0) to busy servers.
Record assignment: Task 2 → Server 0.

At Time 3:

Task 3 arrives with processing time 2.
Check busy servers: (3, 2, 2) now has finish time 3 which is ≤ current time, so pop it.
Add server 2 back to free servers as (2, 2).
Free servers now: (2, 2) and (3, 1).
Select the optimal server: (2, 2) (server 2).
Calculate finish time: 3 + 2 = 5.
Remove (2, 2) from free servers and add (5, 2, 2) to busy servers.
Record assignment: Task 3 → Server 2.

At Time 4:

Task 4 arrives with processing time 1.
Check busy servers: The smallest finish times in busy servers are both 5 (from (5, 3, 0) and (5, 2, 2)), so no server is free at time 4.
Free server available: (3, 1) (server 1).
Select server: (3, 1) is chosen.
Calculate finish time: 4 + 1 = 5.
Remove (3, 1) from free servers and add (5, 3, 1) to busy servers.
Record assignment: Task 4 → Server 1.

At Time 5:

Task 5 arrives with processing time 2.
Check busy servers: All busy servers have finish time 5 now: (5, 3, 0), (5, 2, 2), and (5, 3, 1). Since current time is 5, all these servers are free.
Remove all entries with finish time 5 and add them back to the free servers heap. Free servers become: (2, 2), (3, 0), (3, 1).
Select the optimal server: (2, 2) (server 2).
Calculate finish time: 5 + 2 = 7.
Remove (2, 2) from free servers and add (7, 2, 2) to busy servers.
Record assignment: Task 5 → Server 2.

Step 4: Final Result

The recorded assignments are:
Task 0 → Server 2
Task 1 → Server 2
Task 2 → Server 0
Task 3 → Server 2
Task 4 → Server 1
Task 5 → Server 2
The final answer array is: [2, 2, 0, 2, 1, 2].

Code for All Languages

C++

class Solution {
public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        int n = servers.size();
        int m = tasks.size();
        vector<int> ans(m, 0);
        
        // Min-heap for free servers: (weight, index)
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> freeServers;
        // Min-heap for busy servers: (finish time, weight, index)
        priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> busyServers;
        
        // Step 1: Initialize the free servers heap with all servers.
        for (int i = 0; i < n; i++) {
            freeServers.push({servers[i], i});
        }
        
        // Current time in the simulation.
        long long time = 0;
        
        // Process each task one by one.
        for (int i = 0; i < m; i++) {
            // The task arrives at time i. Make sure current time is at least i.
            time = max(time, (long long)i);
            
            // Step 4: Free up servers that have completed their tasks by the current time.
            while (!busyServers.empty() && get<0>(busyServers.top()) <= time) {
                auto [finishTime, weight, idx] = busyServers.top();
                busyServers.pop();
                freeServers.push({weight, idx});
            }
            
            // Step 6: If no servers are free, jump time forward to the next available server.
            if (freeServers.empty()) {
                time = get<0>(busyServers.top());
                while (!busyServers.empty() && get<0>(busyServers.top()) <= time) {
                    auto [finishTime, weight, idx] = busyServers.top();
                    busyServers.pop();
                    freeServers.push({weight, idx});
                }
            }
            
            // Step 5: Assign the task to the optimal free server.
            auto [weight, idx] = freeServers.top();
            freeServers.pop();
            ans[i] = idx;
            // The server will be busy until time + tasks[i].
            busyServers.push({time + tasks[i], weight, idx});
        }
        
        // Step 8: Return the answer array.
        return ans;
    }
};

Java

class Solution {
    // Class to represent a free server with its weight and index.
    class FreeServer {
        int weight, idx;
        FreeServer(int weight, int idx) {
            this.weight = weight;
            this.idx = idx;
        }
    }

    // Class to represent a busy server with its finish time, weight, and index.
    class BusyServer {
        long finishTime;
        int weight, idx;
        BusyServer(long finishTime, int weight, int idx) {
            this.finishTime = finishTime;
            this.weight = weight;
            this.idx = idx;
        }
    }

    public int[] assignTasks(int[] servers, int[] tasks) {
        int n = servers.length, m = tasks.length;
        int[] ans = new int[m];

        // Priority queue for free servers.
        // Sort by weight, then by index.
        PriorityQueue<FreeServer> freeServers = new PriorityQueue<>((a, b) -> {
            if (a.weight != b.weight)
                return a.weight - b.weight;
            return a.idx - b.idx;
        });

        // Priority queue for busy servers.
        // Sort by finish time, then by weight, then by index.
        PriorityQueue<BusyServer> busyServers = new PriorityQueue<>((a, b) -> {
            if (a.finishTime != b.finishTime)
                return Long.compare(a.finishTime, b.finishTime);
            if (a.weight != b.weight)
                return a.weight - b.weight;
            return a.idx - b.idx;
        });

        // Initialize free servers with all servers.
        for (int i = 0; i < n; i++) {
            freeServers.offer(new FreeServer(servers[i], i));
        }

        long time = 0;
        // Process each task one by one.
        for (int i = 0; i < m; i++) {
            // The task arrives at time i.
            time = Math.max(time, i);

            // Free up all servers that have completed their tasks by the current time.
            while (!busyServers.isEmpty() && busyServers.peek().finishTime <= time) {
                BusyServer bs = busyServers.poll();
                freeServers.offer(new FreeServer(bs.weight, bs.idx));
            }

            // If no servers are free, fast-forward time to the next available server.
            if (freeServers.isEmpty()) {
                time = busyServers.peek().finishTime;
                while (!busyServers.isEmpty() && busyServers.peek().finishTime <= time) {
                    BusyServer bs = busyServers.poll();
                    freeServers.offer(new FreeServer(bs.weight, bs.idx));
                }
            }

            // Assign the current task to the optimal free server.
            FreeServer fs = freeServers.poll();
            ans[i] = fs.idx;
            // The server will be busy until time + tasks[i].
            busyServers.offer(new BusyServer(time + tasks[i], fs.weight, fs.idx));
        }

        return ans;
    }
}

Python

import heapq
from typing import List

class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        n, m = len(servers), len(tasks)
        ans = [0] * m
        
        # Initialize the free servers heap with tuples (weight, index)
        free_servers = []
        for i, weight in enumerate(servers):
            heapq.heappush(free_servers, (weight, i))
        
        # Initialize the busy servers heap with tuples (finish time, weight, index)
        busy_servers = []
        
        # Current time in the simulation
        time = 0
        
        for i in range(m):
            # Task i arrives at time i; ensure current time is at least i.
            time = max(time, i)
            
            # Free up servers that have completed their tasks by the current time.
            while busy_servers and busy_servers[0][0] <= time:
                finish_time, weight, idx = heapq.heappop(busy_servers)
                heapq.heappush(free_servers, (weight, idx))
            
            # If no servers are free, fast-forward time to the next available server.
            if not free_servers:
                time = busy_servers[0][0]
                while busy_servers and busy_servers[0][0] <= time:
                    finish_time, weight, idx = heapq.heappop(busy_servers)
                    heapq.heappush(free_servers, (weight, idx))
            
            # Assign the task to the optimal free server.
            weight, idx = heapq.heappop(free_servers)
            ans[i] = idx
            # The server will be busy until time + tasks[i].
            heapq.heappush(busy_servers, (time + tasks[i], weight, idx))
        
        return ans

Javascript

// PriorityQueue implementation using a binary heap.
class PriorityQueue {
  constructor(comparator = (a, b) => a - b) {
    this.heap = [];
    this.comparator = comparator;
  }
  
  size() {
    return this.heap.length;
  }
  
  isEmpty() {
    return this.heap.length === 0;
  }
  
  peek() {
    return this.heap[0];
  }
  
  push(value) {
    this.heap.push(value);
    this._heapifyUp();
  }
  
  pop() {
    if (this.isEmpty()) return null;
    const top = this.peek();
    const bottom = this.heap.pop();
    if (!this.isEmpty()) {
      this.heap[0] = bottom;
      this._heapifyDown();
    }
    return top;
  }
  
  _heapifyUp() {
    let index = this.heap.length - 1;
    const element = this.heap[index];
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.comparator(element, this.heap[parentIndex]) < 0) {
        this.heap[index] = this.heap[parentIndex];
        index = parentIndex;
      } else {
        break;
      }
    }
    this.heap[index] = element;
  }
  
  _heapifyDown() {
    let index = 0;
    const length = this.heap.length;
    const element = this.heap[index];
    while (true) {
      let leftIndex = 2 * index + 1;
      let rightIndex = 2 * index + 2;
      let swapIndex = index;
      
      if (leftIndex < length && this.comparator(this.heap[leftIndex], this.heap[swapIndex]) < 0) {
        swapIndex = leftIndex;
      }
      if (rightIndex < length && this.comparator(this.heap[rightIndex], this.heap[swapIndex]) < 0) {
        swapIndex = rightIndex;
      }
      if (swapIndex === index) break;
      
      [this.heap[index], this.heap[swapIndex]] = [this.heap[swapIndex], this.heap[index]];
      index = swapIndex;
    }
  }
}

var assignTasks = function(servers, tasks) {
  const n = servers.length, m = tasks.length;
  const ans = new Array(m);
  
  // Priority queue for free servers, sorted by weight then index.
  const freeServers = new PriorityQueue((a, b) => {
    if (a.weight !== b.weight) return a.weight - b.weight;
    return a.idx - b.idx;
  });
  
  // Priority queue for busy servers, sorted by finishTime, then weight, then index.
  const busyServers = new PriorityQueue((a, b) => {
    if (a.finishTime !== b.finishTime) return a.finishTime - b.finishTime;
    if (a.weight !== b.weight) return a.weight - b.weight;
    return a.idx - b.idx;
  });
  
  // Initialize the free servers queue with all servers.
  for (let i = 0; i < n; i++) {
    freeServers.push({ weight: servers[i], idx: i });
  }
  
  let time = 0;
  for (let i = 0; i < m; i++) {
    // Each task arrives at time i.
    time = Math.max(time, i);
    
    // Free up all busy servers that have finished by current time.
    while (!busyServers.isEmpty() && busyServers.peek().finishTime <= time) {
      const freed = busyServers.pop();
      freeServers.push({ weight: freed.weight, idx: freed.idx });
    }
    
    // If no free server is available, jump time forward.
    if (freeServers.isEmpty()) {
      time = busyServers.peek().finishTime;
      while (!busyServers.isEmpty() && busyServers.peek().finishTime <= time) {
        const freed = busyServers.pop();
        freeServers.push({ weight: freed.weight, idx: freed.idx });
      }
    }
    
    // Assign the current task to the best available free server.
    const server = freeServers.pop();
    ans[i] = server.idx;
    // Mark the server as busy until time + tasks[i].
    busyServers.push({
      finishTime: time + tasks[i],
      weight: server.weight,
      idx: server.idx
    });
  }
  
  return ans;
};

Process Tasks Using Servers complexity analysis:Time Complexity O(n + m log n).

Initialization:
Building the free servers heap from the servers array takes O(n) time if we use an efficient heapify method. If servers are inserted one by one, it would take O(n log n), but typically heapify is preferred.
Processing Each Task:
For every task in the tasks array (m tasks in total), several heap operations are performed. Each task may require popping an element from the free servers heap and later inserting the server into the busy servers heap. Additionally, when a server completes its task, it is removed from the busy servers heap and added back to the free servers heap. Each of these heap operations costs O(log n) time.
Total Heap Operations:
Since each task leads to a constant number of heap operations (at most one pop and one push for the free servers heap and similarly for the busy servers heap), the overall work per task is O(log n). This gives a combined complexity for processing all tasks as O(m log n).
Final Complexity:
Including the initialization, the total time complexity is O(n + m log n). Since m is typically larger than n in most cases, the dominant term is O(m log n).

Process Tasks Using Servers complexity analysis: Space Complexity O(n + m)

Auxiliary Space Complexity

The primary auxiliary space is used by the two min-heaps.
The free servers heap stores up to n elements (one per server), requiring O(n) space.
The busy servers heap similarly stores up to n elements at worst, also requiring O(n) space.
Other variables use constant space.
Therefore, the total auxiliary space (excluding input and output) is O(n).

Total Space Complexity

The input arrays for servers and tasks require O(n) and O(m) space, respectively.
The output array that records task assignments requires O(m) space.
Combining these with the auxiliary space, the overall total space complexity is O(n + m).

Preface

Online Judges

Time & Space Complexity

Control Flow Practice

Array Basics

String Basics

Matrix Basics

Math Basics

Recursion Basics

Sorting

Two Pointer

Prefix Sum

Matrix

Hashing

Sliding Window

Linked List

Stack

Queue

Binary Search

Bit Manipulation

Recursion and Backtracking

Trees

Heaps

Tries

Greedy

Dynamic Programming

Graphs

String Matching Algorithms

Combinatorics

Geometry

Game Theory

Advanced Algorithm