Cache with expiry, priority and LRU eviction

Implement a fixed-capacity key-value cache, PriorityExpiryLRUCache. Every item stores a value, an integer priority, and an expiry time. When a new key arrives and the cache is full, exactly one item is evicted, following these rules in order:

1. If any item has expired (expiry <= now), evict an expired item. Choose the one with the earliest expiry.
2. Otherwise, evict an item with the lowest priority.
3. If several items share that lowest priority, evict the least recently used one. Both get and set count as a use.

API

class PriorityExpiryLRUCache:
    def __init__(self, capacity: int) -> None: ...
    def get(self, key: str, now: int) -> Any | None: ...
    def set(self, key: str, value: Any, priority: int, expiry: int, now: int) -> None: ...

• now is the current time, passed in so behavior is deterministic.
• get returns the value and marks the key as recently used. It returns None for a missing key. It also returns None for an expired key, and removes that key.
• set on an existing key replaces its value, priority and expiry. It never causes an eviction.
• set on a new key evicts one item first if the cache is at capacity.

Constraints

• 1 <= capacity <= 10^5; up to 10^6 calls in total.
• Aim for get in O(1) and set in O(log n), not an O(n) scan per eviction.

Example 1

Capacity 2.

set("cpu", 1, priority=4, expiry=30, now=0)
set("gpu", 2, priority=8, expiry=5,  now=0)
set("ram", 3, priority=1, expiry=30, now=10)  # gpu expired at 5: evict gpu
                                               # cache: {cpu, ram}

gpu had the higher priority but had expired, so it goes first.

Example 2

Capacity 3. Nothing expires before time 100.

set("a", "A", priority=2, expiry=100, now=0)
set("b", "B", priority=2, expiry=100, now=1)
set("c", "C", priority=6, expiry=100, now=2)
get("a", now=3)                               # returns "A"; b is now the LRU at priority 2
set("d", "D", priority=5, expiry=100, now=4)  # evict b
                                              # cache: {a, c, d}