Constraints

• 0 <= len(user_accounts) <= 100000
• Account names are unique.
• 0 <= duration <= 1000000000
• account_date may be any integer day value.
• send_schedule contains at most 100 negative integer offset keys.
• Negative offset keys are strictly less than 0.

Examples

Solution

def solution(send_schedule, user_accounts):
    events = []

    for account in user_accounts:
        name = account['name']
        plan = account['plan']
        begin = account['account_date']
        end = begin + account['duration']

        if 'start' in send_schedule:
            events.append((begin, 1, 0, name, send_schedule['start'], plan))

        for key, label in send_schedule.items():
            if type(key) is int and key < 0:
                events.append((end + key, 2, key, name, label, plan))

        if 'end' in send_schedule:
            events.append((end, 3, 0, name, send_schedule['end'], plan))

    events.sort(key=lambda event: (event[0], event[1], event[2], event[3]))

    result = []
    for time, _priority, _offset, name, label, plan in events:
        result.append(f'{time}: [{label}] Subscription for {name} ({plan})')
    return result

Time complexity: O(NK log(NK)), where N is the number of accounts and K is the number of scheduled labels per account, including start/end and relative offsets.. Space complexity: O(NK) for the generated event list..

Hints

1. Convert every account notification into a sortable event tuple.
2. The sort key should encode both timestamp and the required same-timestamp priority rules.

Constraints

• 0 <= len(user_accounts) <= 100000
• 0 <= len(changes1) <= 100000
• Account names are unique.
• Every change references an existing account.
• At most one plan change exists for the same account at the same timestamp.
• send_schedule contains at most 100 negative integer offset keys.
• Negative offset keys are strictly less than 0.

Examples

Solution

def solution(send_schedule, user_accounts, changes1):
    current_plan = {}
    events = []

    for account in user_accounts:
        name = account['name']
        current_plan[name] = account['plan']
        begin = account['account_date']
        end = begin + account['duration']

        if 'start' in send_schedule:
            events.append((begin, 1, 0, name, 'scheduled', send_schedule['start'], None))

        for key, label in send_schedule.items():
            if type(key) is int and key < 0:
                events.append((end + key, 2, key, name, 'scheduled', label, None))

        if 'end' in send_schedule:
            events.append((end, 3, 0, name, 'scheduled', send_schedule['end'], None))

    for change in changes1:
        name = change['name']
        new_plan = change['new_plan']
        change_date = change['change_date']
        events.append((change_date, 0, 0, name, 'change', None, new_plan))

    events.sort(key=lambda event: (event[0], event[1], event[2], event[3]))

    result = []
    for time, _priority, _offset, name, kind, label, new_plan in events:
        if kind == 'change':
            current_plan[name] = new_plan
            result.append(f'{time}: [Changed] Subscription for {name} ({new_plan})')
        else:
            result.append(f'{time}: [{label}] Subscription for {name} ({current_plan[name]})')

    return result

Time complexity: O((NK + M) log(NK + M)), where N is the number of accounts, K is the number of scheduled labels per account, and M is the number of plan changes.. Space complexity: O(NK + M) for the event list and O(N) for current plans..

Hints

1. You can still create a single global event list, but change events must be processed before scheduled notifications at the same time.
2. Store the current plan for each account separately from the event list so later events see updates.

Constraints

• 0 <= len(user_accounts) <= 100000
• 0 <= len(changes) <= 100000
• Account names are unique.
• Every change or renewal references an existing account.
• At most one plan change and at most one renewal exist for the same account at the same timestamp.
• extension is a positive integer.
• send_schedule contains at most 100 negative integer offset keys.
• Negative offset keys are strictly less than 0.

Examples

Solution

def solution(send_schedule, user_accounts, changes):
    import heapq

    accounts = {}
    heap = []
    sequence = 0

    offsets = []
    for key, label in send_schedule.items():
        if type(key) is int and key < 0:
            offsets.append((key, label))

    def push(time, priority, offset_order, name, kind, label=None, value=None, version=None):
        nonlocal sequence
        heapq.heappush(heap, (time, priority, offset_order, name, sequence, kind, label, value, version))
        sequence += 1

    def schedule_end_relative_events(name, current_time=None):
        account = accounts[name]
        end = account['end']
        version = account['version']

        for offset, label in offsets:
            event_time = end + offset
            if current_time is None or event_time >= current_time:
                push(event_time, 3, offset, name, 'offset', label, None, version)

        if 'end' in send_schedule:
            if current_time is None or end >= current_time:
                push(end, 4, 0, name, 'end', send_schedule['end'], None, version)

    for account in user_accounts:
        name = account['name']
        begin = account['account_date']
        end = begin + account['duration']
        accounts[name] = {
            'plan': account['plan'],
            'end': end,
            'version': 0
        }

        if 'start' in send_schedule:
            push(begin, 2, 0, name, 'start', send_schedule['start'], None, None)

        schedule_end_relative_events(name)

    for change in changes:
        name = change['name']
        change_date = change['change_date']
        if 'new_plan' in change:
            push(change_date, 0, 0, name, 'change', None, change['new_plan'], None)
        else:
            push(change_date, 1, 0, name, 'renew', None, change['extension'], None)

    result = []

    while heap:
        time, _priority, _offset_order, name, _seq, kind, label, value, version = heapq.heappop(heap)

        if name not in accounts:
            continue

        account = accounts[name]

        if kind in ('offset', 'end') and version != account['version']:
            continue

        if kind == 'change':
            account['plan'] = value
            result.append(f'{time}: [Changed] Subscription for {name} ({account["plan"]})')
        elif kind == 'renew':
            result.append(f'{time}: [Renewed] Subscription for {name} ({account["plan"]})')
            account['end'] += value
            account['version'] += 1
            schedule_end_relative_events(name, time)
        elif kind == 'start':
            result.append(f'{time}: [{label}] Subscription for {name} ({account["plan"]})')
        else:
            result.append(f'{time}: [{label}] Subscription for {name} ({account["plan"]})')

    return result

Time complexity: O((NK + M + RK) log(NK + M + RK)), where N is accounts, K is scheduled labels per account, M is total changes, and R is the number of renewals. Each renewal may reschedule all relative/end events for that account.. Space complexity: O(NK + M + RK) for heap entries, including stale entries that are later skipped, plus O(N) account state..

Hints

1. A min-heap works well because renewals can create newly scheduled future events while the simulation is running.
2. Use a per-account version number to invalidate old end-relative events after a renewal.