Problem Description

You have a mountain with a given height mountainHeight and multiple workers who can work simultaneously to reduce this height to 0. Each worker has their own working speed defined in the array workerTimes.

For each worker i, the time required to reduce the mountain height follows a specific pattern:

• To reduce height by 1: takes workerTimes[i] seconds
• To reduce height by 2: takes workerTimes[i] + workerTimes[i] * 2 seconds
• To reduce height by 3: takes workerTimes[i] + workerTimes[i] * 2 + workerTimes[i] * 3 seconds
• In general, to reduce height by x: takes workerTimes[i] * (1 + 2 + ... + x) seconds

The key insight is that this forms an arithmetic series. To reduce the height by x, worker i needs: workerTimes[i] * (1 + 2 + ... + x) = workerTimes[i] * x * (x + 1) / 2 seconds

Since workers operate simultaneously, the total time taken is determined by when all workers collectively reduce the mountain height to 0. Each worker can reduce a different amount of height, and we need to find the optimal distribution that minimizes the total time.

The solution uses binary search on the time t. For a given time t, we calculate how much height each worker can reduce. Using the formula above, if worker i reduces height by h' in time t, then: workerTimes[i] * h' * (h' + 1) / 2 ≤ t

Solving this quadratic inequality gives us the maximum height each worker can reduce in time t. The binary search finds the minimum time where the sum of all heights reduced by workers is at least mountainHeight.

Intuition

The key observation is that if we can reduce the mountain to height 0 in t seconds, then we can definitely do it in any time greater than t. This monotonic property immediately suggests binary search on the answer.

Why binary search on time? Consider the alternative - trying to directly calculate the optimal height distribution among workers. This becomes a complex optimization problem because each worker has different efficiency and the cost function is quadratic. However, if we fix the time t, we can easily calculate the maximum height each worker can reduce independently.

For a fixed time t, each worker works independently and we want to maximize their contribution. Given worker i has t seconds, we need to find the maximum height h' they can reduce where: workerTimes[i] * (1 + 2 + ... + h') ≤ t

Using the arithmetic series sum formula: workerTimes[i] * h' * (h' + 1) / 2 ≤ t

This is a quadratic inequality in h'. Rearranging: h'² + h' - 2t/workerTimes[i] ≤ 0

Using the quadratic formula and taking the positive root: h' ≤ (-1 + √(1 + 8t/workerTimes[i])) / 2

Which simplifies to: h' ≤ ⌊√(2t/workerTimes[i] + 1/4) - 1/2⌋

Once we can calculate each worker's maximum contribution for a given time t, we simply sum these contributions. If the total is at least mountainHeight, then time t is sufficient. Otherwise, we need more time.

The binary search bounds are straightforward: the minimum time is close to 0, and the maximum can be estimated by considering the worst case where one slow worker does all the work. Since workerTimes[i] ≤ 10^6 and mountainHeight ≤ 10^5, the upper bound of 10^16 is safe.

Learn more about Greedy, Math, Binary Search and Heap (Priority Queue) patterns.

Solution Approach

The solution implements a binary search to find the minimum time required. Here's how the implementation works:

Binary Search Setup: We use bisect_left to find the leftmost position where the condition becomes True. The search range is from 0 to 10^16, which safely covers all possible time values.

Check Function: The check(t) function determines if time t is sufficient for workers to reduce the mountain to height 0:

1. Initialize a counter h = 0 to track the total height reduction

2. For each worker with time workerTimes[i], calculate the maximum height they can reduce using the formula:

   h += int(sqrt(2 * t / wt + 1 / 4) - 1 / 2)

   This formula comes from solving the quadratic inequality: wt * h' * (h' + 1) / 2 ≤ t

   Which gives us: h' ≤ √(2t/wt + 1/4) - 1/2

3. Return True if the total height reduction h >= mountainHeight

Why This Formula Works: Given a worker needs wt * h' * (h' + 1) / 2 seconds to reduce height by h', we rearrange to find the maximum h' possible in time t:

• Start with: wt * h' * (h' + 1) / 2 ≤ t
• Multiply by 2: wt * h' * (h' + 1) ≤ 2t
• Expand: wt * h'² + wt * h' ≤ 2t
• Rearrange: h'² + h' - 2t/wt ≤ 0
• Complete the square: (h' + 1/2)² ≤ 2t/wt + 1/4
• Take square root: h' + 1/2 ≤ √(2t/wt + 1/4)
• Solve for h': h' ≤ √(2t/wt + 1/4) - 1/2

Binary Search Execution: The bisect_left function efficiently finds the minimum time where check(t) returns True. It performs binary search on the range [0, 10^16], using the key=check parameter to evaluate each midpoint.

The time complexity is O(n * log(10^16)) where n is the number of workers, as we perform the check function O(log(10^16)) times, and each check takes O(n) time to iterate through all workers.

Example Walkthrough

Let's walk through a small example with mountainHeight = 10 and workerTimes = [2, 4].

Step 1: Understanding Worker Capabilities

Worker 0 (time = 2):

• Reduce by 1: takes 2×1 = 2 seconds
• Reduce by 2: takes 2×(1+2) = 6 seconds
• Reduce by 3: takes 2×(1+2+3) = 12 seconds
• Reduce by 4: takes 2×(1+2+3+4) = 20 seconds

Worker 1 (time = 4):

• Reduce by 1: takes 4×1 = 4 seconds
• Reduce by 2: takes 4×(1+2) = 12 seconds
• Reduce by 3: takes 4×(1+2+3) = 24 seconds

Step 2: Binary Search Process

We binary search on time from 0 to 10^16. Let's check some key time values:

Check t = 10:

• Worker 0: Using formula h' ≤ √(2×10/2 + 1/4) - 1/2 = √(10.25) - 0.5 ≈ 2.7, so can reduce 2 units
• Worker 1: Using formula h' ≤ √(2×10/4 + 1/4) - 1/2 = √(5.25) - 0.5 ≈ 1.8, so can reduce 1 unit
• Total reduction: 2 + 1 = 3 < 10 ❌ (not enough)

Check t = 20:

• Worker 0: h' ≤ √(2×20/2 + 1/4) - 1/2 = √(20.25) - 0.5 ≈ 4.0, so can reduce 4 units
• Worker 1: h' ≤ √(2×20/4 + 1/4) - 1/2 = √(10.25) - 0.5 ≈ 2.7, so can reduce 2 units
• Total reduction: 4 + 2 = 6 < 10 ❌ (not enough)

Check t = 40:

• Worker 0: h' ≤ √(2×40/2 + 1/4) - 1/2 = √(40.25) - 0.5 ≈ 5.8, so can reduce 5 units
• Worker 1: h' ≤ √(2×40/4 + 1/4) - 1/2 = √(20.25) - 0.5 ≈ 4.0, so can reduce 4 units
• Total reduction: 5 + 4 = 9 < 10 ❌ (not enough)

Check t = 42:

• Worker 0: h' ≤ √(2×42/2 + 1/4) - 1/2 = √(42.25) - 0.5 ≈ 6.0, so can reduce 6 units
• Worker 1: h' ≤ √(2×42/4 + 1/4) - 1/2 = √(21.25) - 0.5 ≈ 4.1, so can reduce 4 units
• Total reduction: 6 + 4 = 10 ✓ (sufficient!)

Step 3: Verification

Let's verify t = 42 is correct:

• Worker 0 reduces 6 units: takes 2×(1+2+3+4+5+6) = 2×21 = 42 seconds
• Worker 1 reduces 4 units: takes 4×(1+2+3+4) = 4×10 = 40 seconds
• Both finish within 42 seconds, and 6 + 4 = 10 (mountain fully reduced)

Binary search continues narrowing down between values where the check fails and succeeds, ultimately finding that 42 is the minimum time needed.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log M), where n is the number of workers (length of workerTimes), and M is the upper bound of the binary search range, which is 10^16 in this problem.

The analysis breaks down as follows:

• The bisect_left function performs a binary search over the range [0, 10^16), which requires O(log M) iterations where M = 10^16
• For each iteration of the binary search, the check function is called
• Inside the check function, we iterate through all n workers in workerTimes, performing a constant-time calculation (square root and arithmetic operations) for each worker
• Therefore, each call to check takes O(n) time
• The total time complexity is O(n) × O(log M) = O(n × log M)

Space Complexity: O(1)

The space analysis:

• The check function only uses a constant amount of extra space for the variable h and loop variable
• The binary search itself only requires constant space for maintaining search boundaries
• No additional data structures are created that scale with the input size
• Therefore, the overall space complexity is O(1) (constant space)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Binary Search Upper Bound

Pitfall: Using an inadequate upper bound for binary search can lead to incorrect results for large inputs. The formula workerTime * n * (n + 1) / 2 grows quadratically, and with large mountainHeight and workerTimes, the required time can be substantial.

Solution: Use a sufficiently large upper bound. A safe approach is to calculate the worst-case scenario:

# Calculate a proper upper bound
max_worker_time = max(workerTimes)
# Worst case: single slowest worker does all the work
upper_bound = max_worker_time * mountainHeight * (mountainHeight + 1) // 2

2. Floating Point Precision Errors

Pitfall: The quadratic formula involves square roots and division, which can introduce floating-point precision errors:

# Potential precision issues
max_rounds = int(sqrt(2 * time_limit / worker_time + 0.25) - 0.5)

When time_limit is very large or worker_time is very small, the calculation might lose precision.

Solution: Add a small epsilon for comparison or use integer arithmetic where possible:

def can_complete_in_time(time_limit: int) -> bool:
    total_height_reduced = 0
  
    for worker_time in workerTimes:
        # Binary search for max_rounds instead of using floating-point formula
        left, right = 0, mountainHeight
        while left < right:
            mid = (left + right + 1) // 2
            if worker_time * mid * (mid + 1) // 2 <= time_limit:
                left = mid
            else:
                right = mid - 1
        total_height_reduced += left
  
    return total_height_reduced >= mountainHeight

3. Incorrect Quadratic Formula Application

Pitfall: Misapplying the quadratic formula or using the wrong root. The inequality wt * h * (h + 1) / 2 ≤ t leads to a quadratic equation, and choosing the wrong root or making algebraic errors is common.

Solution: Verify the formula derivation and always take the positive root:

# Correct formula with explicit steps
discriminant = 1 + 8 * time_limit / worker_time
if discriminant < 0:
    max_rounds = 0
else:
    # We need the positive root: (-1 + sqrt(discriminant)) / 2
    max_rounds = int((-1 + sqrt(discriminant)) / 2)

4. Division by Zero

Pitfall: If any workerTimes[i] is 0, division by zero occurs in the formula.

Solution: Add validation for edge cases:

def can_complete_in_time(time_limit: int) -> bool:
    total_height_reduced = 0
  
    for worker_time in workerTimes:
        if worker_time == 0:
            # Worker with 0 time can reduce infinite height instantly
            return True
        max_rounds = int(sqrt(2 * time_limit / worker_time + 0.25) - 0.5)
        total_height_reduced += max_rounds
  
    return total_height_reduced >= mountainHeight

5. Early Termination Optimization Missing

Pitfall: Continuing to calculate even after we've already reduced enough height wastes computation.

Solution: Add early termination:

def can_complete_in_time(time_limit: int) -> bool:
    total_height_reduced = 0
  
    for worker_time in workerTimes:
        max_rounds = int(sqrt(2 * time_limit / worker_time + 0.25) - 0.5)
        total_height_reduced += max_rounds
      
        # Early termination if we've already reduced enough
        if total_height_reduced >= mountainHeight:
            return True
  
    return total_height_reduced >= mountainHeight