1648. Sell Diminishing-Valued Colored Balls

The objective is to maximize profit when selling balls whose values decrease by 1 after each sale. The optimal approach is a greedy strategy where we always sell the currently most valuable balls available.

By sorting the inventory in descending order, we can visualize the stock as columns. We process horizontal layers of these columns. For each step, we calculate how many balls are in the current layer across all columns with the maximum height. We determine if we can sell all balls in that layer or only part of it based on the remaining order count. Arithmetic series formulas are used to efficiently calculate the sum of values for these layers.

class Solution:
    def maxProfit(self, inventory: List[int], orders: int) -> int:
        MOD = 10**9 + 7
        
        # Sort in descending order to process highest values first
        inventory.sort(reverse=True)
        # Append a sentinel value to handle the last group of balls
        inventory.append(0)
        
        max_profit = 0
        colors_count = 1 # Number of colors having the current maximum value
        
        for i in range(len(inventory) - 1):
            if inventory[i] > inventory[i+1]:
                # Difference in height between the current layer and the next
                height_diff = inventory[i] - inventory[i+1]
                
                # Check if we can fulfill orders with the current height difference
                if colors_count * height_diff < orders:
                    # Sum of arithmetic series: count * (start + end) * height / 2
                    max_profit += colors_count * (inventory[i] + inventory[i+1] + 1) * height_diff // 2
                    orders -= colors_count * height_diff
                else:
                    # We cannot sell the full layer; calculate the remaining part
                    full_layers, remainder = divmod(orders, colors_count)
                    
                    # Profit from the full layers we can sell
                    max_profit += colors_count * (inventory[i] + (inventory[i] - full_layers + 1)) * full_layers // 2
                    # Profit from the remaining balls
                    max_profit += remainder * (inventory[i] - full_layers)
                    
                    return max_profit % MOD
            
            colors_count += 1

1921. Eliminate Maximum Number of Monsters

This problem requires us to eliminate monsters before they reach the city. We can eliminate exactly one monster per minute. The core insight is to determine the exact minute each monster arrives and process them in chronological order.

We calculate the time it takes for each monster to reach the city using ceiling division. By sorting these arrival times, we can iterate through them. If a monster's arrival time is less than or equal to the current minute (which represents the number of monsters we have already eliminated), we fail. Otherwise, we continue until all monsters are eliminated.

class Solution:
    def eliminateMaximum(self, distances: List[int], speeds: List[int]) -> int:
        # Calculate the minute each monster arrives at the city
        time_to_arrival = []
        for i in range(len(distances)):
            # Ceiling division: (distance + speed - 1) // speed
            time = (distances[i] + speeds[i] - 1) // speeds[i]
            time_to_arrival.append(time)
            
        # Sort by arrival time
        time_to_arrival.sort()
        
        # Iterate and check if we can kill the monster before it arrives
        for minute, arrival in enumerate(time_to_arrival):
            if arrival <= minute:
                return minute
                
        return len(time_to_arrival)

1798. Maximum Number of Consecutive Values You Can Make

We need to detremine the maximum number of consecutive values starting from 0 that can be formed using a set of coins. A greedy approach works here by sorting the coins and iteratively expanding the reachable range.

We maintain a variable representing the maximum consecutive value we can form (initially 0). For each coin, if the coin's value is greater than the current maximum reachable value plus one, there is a gap that cannot be filled, and we stop. Otherwise, we add the coin's value to our range, effectively extending the maximum consecutive value we can create.

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        coins.sort()
        # Represents that we can currently make all values in [0, max_reachable]
        max_reachable = 0
        
        for coin in coins:
            # If the coin is too large, we cannot form (max_reachable + 1)
            if coin > max_reachable + 1:
                break
            # Otherwise, we can extend the range
            max_reachable += coin
            
        # Return the count of values: 0 to max_reachable inclusive
        return max_reachable + 1