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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Rounds to Complete All Tasks

Difficulty: Medium

Problem Description

You are given a 0-indexed integer array tasks, where tasks[i] represents the difficulty level of a task. In each round, you can complete either 2 or 3 tasks of the same difficulty level. Return the minimum rounds required to complete all the tasks, or -1 if it is not possible to complete all the tasks.

Key Insights

  • You can only complete tasks in groups of 2 or 3.
  • If a difficulty level has only 1 task, it is impossible to complete those tasks.
  • The optimal way to minimize rounds is to maximize the number of tasks completed in each round (prefer completing 3 tasks when possible).
  • Use a frequency counter to count occurrences of each difficulty level.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a hash table (or dictionary) to count the frequency of each difficulty level. For each unique difficulty level, we can calculate the minimum rounds required based on its frequency:

  1. If the frequency is 1, return -1 as it's impossible to complete.
  2. For frequencies greater than 1:
    • Use as many groups of 3 as possible.
    • Use groups of 2 for any remaining tasks.
  3. Sum all the rounds for each difficulty level to get the total minimum rounds.

Code Solutions

from collections import Counter

def minimumRounds(tasks):
    freq = Counter(tasks)
    rounds = 0
    
    for count in freq.values():
        if count == 1:
            return -1  # Impossible to complete this task
        
        # Calculate rounds using groups of 3 and possibly 2
        rounds += count // 3  # Groups of 3
        if count % 3 > 0:      # Remaining tasks
            rounds += 1        # Need an extra round for remaining tasks
            
    return rounds
← Back to All Questions