We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Rounds to Complete All Tasks

Number: 2362

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer array tasks where tasks[i] represents the difficulty level of a task, determine the minimum number of rounds required to complete all tasks. In each round, you can complete either 2 or 3 tasks of the same difficulty level. Return -1 if it is not possible to complete all tasks under these conditions.

Key Insights

  • Count the frequency of each task difficulty.
  • For each difficulty level, if the frequency is 1 then it is impossible to complete those tasks.
  • For frequencies greater than 1, optimally use rounds of 3 tasks wherever possible to minimize the number of rounds.
  • Handle remainders carefully:
    • If frequency modulo 3 is 0, use frequency/3 rounds.
    • If frequency modulo 3 is 1, reduce one group of 3 to combine with the remaining 1 (i.e., (frequency - 4)/3 + 2 rounds).
    • If frequency modulo 3 is 2, the answer is frequency//3 + 1 rounds.

Space and Time Complexity

Time Complexity: O(n) where n is the number of tasks, since we iterate over the list once to count frequencies and then over the distinct difficulties. Space Complexity: O(k) where k is the number of unique difficulties (k <= n).

Solution

The approach uses a hash table (or dictionary) to count the frequency of each difficulty level in the tasks array. For each unique difficulty, apply the following logic:

  1. If the frequency is 1, return -1 as it is impossible to group a single task into rounds of 2 or 3.
  2. Otherwise, calculate the minimum number of rounds required using greedy grouping:
    • If frequency % 3 == 0, the number of rounds is frequency / 3.
    • If frequency % 3 == 1, adjust by using one less group of 3 (i.e. frequency - 4) and add two rounds for the remaining 4 tasks.
    • If frequency % 3 == 2, add one extra round to the frequency // 3. This method guarantees the minimum rounds are used to complete the tasks.

Code Solutions

# Python solution with inline comments
def minimumRounds(tasks):
    from collections import Counter
    # Count frequency of each task difficulty
    frequency = Counter(tasks)
    rounds = 0
    
    # Process each difficulty level count
    for count in frequency.values():
        # If only 1 task is available, grouping is impossible.
        if count == 1:
            return -1
        # If remaining tasks can be grouped exactly in threes.
        if count % 3 == 0:
            rounds += count // 3
        # If the remainder after grouping by 3 is 1, then adjust:
        # Use one fewer group of 3 and add two rounds to account for the remaining 4 tasks.
        elif count % 3 == 1:
            rounds += (count - 4) // 3 + 2
        # If the remainder is 2, simply add one extra round.
        else:  # count % 3 == 2
            rounds += count // 3 + 1
    return rounds

# Example usage:
print(minimumRounds([2,2,3,3,2,4,4,4,4,4]))  # Output: 4
print(minimumRounds([2,3,3]))                # Output: -1
← Back to All Questions