Schedule Seller Tasks with Tier-Weighted Round Robin

Problem Statement

In an e-commerce platform, tasks from multiple sellers need to be scheduled for background processing. Each task belongs to a specific seller and has a defined priority level.

Implement the TaskScheduler class:

• __init__(): Initializes the scheduler.
• add_task(task_id: str, seller_id: str, tier: str, priority: int) -> None: Enqueues a new task. tier is either "VIP" or "STANDARD". Priority values are positive integers where smaller numbers represent higher priority (e.g., 1 is higher priority than 2). If a seller's tier is updated by a new task, the seller adopts the most recently provided tier.
• process_next_task() -> Optional[str]: Processes and returns the task_id of the next scheduled task according to the rules below. If there are no tasks across any seller, returns None.

Scheduling Rules

1. Per-Seller Ordering:

   • Within a single seller's backlog, tasks with higher priority (smaller integer) must always be processed before lower-priority tasks.
   • Tasks with the same priority for the same seller must be processed in FIFO (First-In, First-Out) arrival order.

2. Cross-Seller Tier-Weighted Round Robin:

   • Active sellers (sellers with at least one pending task) are served in a round-robin rotation based on their initial activation order.
   • In each round, a seller is granted a quota of tasks they may process:
     • "VIP": up to 2 tasks per turn.
     • "STANDARD": up to 1 task per turn.
   • A seller's turn ends when they exhaust their quota for the round or when their pending queue becomes completely empty, whichever happens first.
   • If a seller still has pending tasks after exhausting their quota, they are moved to the end of the active rotation, and their quota resets to full for their next turn.
   • If a seller exhausts all pending tasks before using their full quota, their turn ends immediately and they are removed from active rotation. If a new task arrives for an inactive seller later, they are appended to the end of the active rotation with a fresh quota.
   • Turn state is persistent across interleaved add_task and process_next_task calls.

Interface

class TaskScheduler:
    def __init__(self):
        pass

    def add_task(self, task_id: str, seller_id: str, tier: str, priority: int) -> None:
        pass

    def process_next_task(self) -> Optional[str]:
        pass

Example

scheduler = TaskScheduler()
scheduler.add_task("T1", "seller_A", "STANDARD", 2)
scheduler.add_task("T2", "seller_B", "VIP", 2)
scheduler.add_task("T3", "seller_B", "VIP", 1)
scheduler.add_task("T4", "seller_B", "VIP", 1)

# Active order: seller_A (quota 1), seller_B (quota 2)
assert scheduler.process_next_task() == "T1"  # seller_A uses quota 1 (now empty, removed)
assert scheduler.process_next_task() == "T3"  # seller_B turn: prio 1 FIFO (T3 before T4), quota left: 1
assert scheduler.process_next_task() == "T4"  # seller_B turn: prio 1 (T4), quota left: 0 -> turn ends
# seller_B still has T2, so seller_B is re-queued as the only active seller
assert scheduler.process_next_task() == "T2"  # seller_B starts new turn, returns T2
assert scheduler.process_next_task() is None  # no tasks left

Constraints

• 1 <= len(task_id), len(seller_id) <= 32
• tier is always "VIP" or "STANDARD".
• 1 <= priority <= 10^5
• At most 10^5 total calls to add_task and process_next_task.