Constraints

• 0 <= start_minute < end_minute <= 1440
• 0 <= pickup_minute <= dropoff_minute <= 1440
• Rate intervals do not overlap, but they may leave gaps in the day
• 1 <= len(rate_intervals), len(trips) <= 100000 is possible, but the day length is fixed at 1440 minutes
• rate_per_minute and per_trip_bonus are non-negative integers

Examples

Solution

def solution(rate_intervals, trips):
    diff = [0] * 1442

    for start, end, rate in rate_intervals:
        diff[start] += rate
        diff[end] -= rate

    per_minute = [0] * 1440
    running = 0
    for minute in range(1440):
        running += diff[minute]
        per_minute[minute] = running

    prefix_pay = [0] * 1441
    for minute in range(1440):
        prefix_pay[minute + 1] = prefix_pay[minute] + per_minute[minute]

    total = 0
    for pickup, dropoff, bonus in trips:
        total += prefix_pay[dropoff] - prefix_pay[pickup] + bonus

    return total

Time complexity: O(len(rate_intervals) + len(trips) + 1440). Space complexity: O(1440).

Hints

1. Because the day has only 1440 minutes, you can precompute the pay rate for every minute of the day.
2. After building per-minute rates, a prefix-sum array lets you answer each trip's time-based pay in O(1).

Constraints

• 1 <= len(operations) <= 200000
• serverId and requestId are non-empty strings
• Servers should be routed in the order they were added among currently active servers
• Duplicate addServer operations are ignored
• removeServer on a missing server is ignored

Examples

Solution

def solution(operations):
    class Node:
        __slots__ = ('sid', 'prev', 'next')

        def __init__(self, sid):
            self.sid = sid
            self.prev = self
            self.next = self

    nodes = {}
    tail = None
    cursor = None
    result = []

    for op in operations:
        action = op[0]

        if action == 'addServer':
            sid = op[1]
            if sid in nodes:
                continue

            node = Node(sid)
            nodes[sid] = node

            if tail is None:
                tail = node
                cursor = node
            else:
                head = tail.next
                node.prev = tail
                node.next = head
                tail.next = node
                head.prev = node
                tail = node

        elif action == 'removeServer':
            sid = op[1]
            node = nodes.pop(sid, None)
            if node is None:
                continue

            if node.next is node:
                tail = None
                cursor = None
                continue

            if cursor is node:
                cursor = node.next

            node.prev.next = node.next
            node.next.prev = node.prev

            if tail is node:
                tail = node.prev

        else:  # route
            if cursor is None:
                result.append(None)
            else:
                result.append(cursor.sid)
                cursor = cursor.next

    return result

Time complexity: O(1) average time per addServer, removeServer, and route operation. Space complexity: O(S), where S is the number of active servers.

Hints

1. Think about keeping a pointer to the next server that should receive traffic.
2. A hash map plus a circular doubly linked list gives O(1) add, remove, and route.

Constraints

• 1 <= len(operations) <= 100000
• 1 <= virtual_nodes <= 1000
• serverId and requestId are non-empty strings
• Use the exact hash function and ring rule described in the statement so routing is deterministic
• Duplicate addServer operations are ignored, and removeServer on a missing server is ignored

Examples

Solution

def solution(operations, virtual_nodes):
    from bisect import bisect_left, insort

    def ring_hash(s):
        total = 0
        for i, ch in enumerate(s):
            total += (i + 1) * ord(ch)
        return total

    ring = []
    server_to_nodes = {}
    result = []

    for op in operations:
        action = op[0]

        if action == 'addServer':
            sid = op[1]
            if sid in server_to_nodes:
                continue

            nodes = []
            for i in range(virtual_nodes):
                entry = (ring_hash(f'{sid}#{i}'), sid, i)
                insort(ring, entry)
                nodes.append(entry)
            server_to_nodes[sid] = nodes

        elif action == 'removeServer':
            sid = op[1]
            nodes = server_to_nodes.pop(sid, None)
            if not nodes:
                continue

            for entry in nodes:
                idx = bisect_left(ring, entry)
                if idx < len(ring) and ring[idx] == entry:
                    ring.pop(idx)

        else:  # route
            request_id = op[1]
            if not ring:
                result.append(None)
                continue

            key = (ring_hash(request_id), '', -1)
            idx = bisect_left(ring, key)
            if idx == len(ring):
                idx = 0
            result.append(ring[idx][1])

    return result

Time complexity: Routing: O(log M). Adding or removing one server: O(V * M) worst-case with Python list insertions/removals, where V is virtual_nodes and M is the current number of virtual nodes on the ring.. Space complexity: O(M), where M is the number of active virtual nodes.

Hints

1. Store all virtual nodes in a sorted structure by hash so you can binary-search the destination for each request.
2. Keep track of which virtual-node entries belong to each server so removal is straightforward.