Problem Overview

Design a CreditTracker class that manages credits with expiration windows. Credits are valid only within a specified time range, and when subtracting credits, you must consume from the credit with the earliest expiration time first.

Methods:

` class CreditTracker: def add_credit(self, start_time: int, end_time: int, credit: int) -> None: """Add credit that is valid from start_time to end_time (exclusive)."""

def subtract_credit(self, time: int, credit: int) -> None:
    """Subtract credit at the given time. Deduct from earliest expiring credit first."""

def check_credit(self, time: int) -> int:
    """Return total available credit at the given time."""

`

Key Constraints:

• Credits are only valid in the window [start_time, end_time)

• When subtracting, always consume from the credit expiring soonest

• Operations may arrive in any order (times are not monotonically increasing)

Important Notes

• This is a greedy algorithm problem with state management

• The core challenge is the subtract_credit method

• Must handle overlapping credit windows correctly

• Edge cases include expired credits and partial deductions

Part 1: Implementation

Example

` tracker = CreditTracker() tracker.add_credit(0, 10, 50) # 50 credits valid from t=0 to t=10 tracker.add_credit(3, 7, 30) # 30 credits valid from t=3 to t=7

tracker.check_credit(5) # Returns 80 (both credits valid at t=5) tracker.subtract_credit(5, 40) # Subtract 40 at t=5

Credit (3,7,30) expires first → subtract 30 from it (now 0)

Credit (0,10,50) expires next → subtract remaining 10 from it (now 40)

tracker.check_credit(5) # Returns 40 (only credit (0,10,40) remains) tracker.check_credit(8) # Returns 40 (credit (3,7) expired, only (0,10,40) valid) `

The core challenge is the subtract_credit method. We need to:

• Find all credits that are valid at the given time

• Sort them by expiration time (earliest first)

• Greedily subtract from the earliest expiring credit

This greedy approach is optimal: by consuming soon-to-expire credits first, we preserve longer-lived credits for future operations.

• Store the credit with its validity window

• Credits are valid in [start_time, end_time) (end_time is exclusive)

• Sum all credits that are valid at the given time

• A credit is valid if: start_time ≤ time < end_time and remaining credit > 0

• Find all credits valid at the given time

• Sort by end_time (earliest expiration first)

• Greedily deduct from earliest expiring credits

• Raise ValueError if insufficient credit available

Store credits as a list of [start_time, end_time, remaining_credit]:

` self.credits: List[List] = []

Each entry: [start_time, end_time, remaining_credit]

`