Count Employees With Unbroken Renewable Access at the Last Timestamp

An access system grants employees time-limited access. Employee i has a fixed access duration limits[i]. The system receives a log of access settings, events. Each event [id, t] means that at time t access is set for employee id, which grants access until time t + limits[id].

Access must be unbroken. A setting can extend an employee's access only while that access is still active. Once an employee's access has run out, it is invalid for good, and later settings for that employee have no effect.

After all events are processed, return the number of employees whose access is valid at the last time point, which is the largest t in events.

Function Signature

def count_active_access(limits: list[int], events: list[list[int]]) -> int:

Rules

• Each employee who has at least one event has an expiry time. Their access is active at time x exactly when x < expiry.
• The first event for employee id, at time t, sets the expiry to t + limits[id].
• A later event for the same employee at time t:
  • if the access is active at t (that is, t < expiry), sets the expiry to t + limits[id];
  • otherwise (t >= expiry), the employee's access has lapsed. This event and every later event for that employee are ignored, and the employee is not counted.
• Events are sorted by non-decreasing t and are processed in the given order.
• Let t_last be the largest t in events. Count the employees who have at least one event, have not lapsed, and whose expiry is greater than t_last. Employees with no events are not counted.

Constraints

• 1 <= len(limits) <= 100000
• 1 <= limits[i] <= 10^9
• 1 <= len(events) <= 100000
• events[j] = [id, t] with 0 <= id < len(limits) and 0 <= t <= 10^9
• events[j][1] <= events[j + 1][1] for every j
• An expiry can reach 2 * 10^9, which exceeds 2^31 - 1; use 64-bit integers.

Examples

Example 1

Input:  limits = [5, 3, 10]
        events = [[0, 1], [1, 2], [0, 4], [1, 6], [2, 7], [0, 8]]
Output: 2

Employee 0 gets expiry 6 at time 1, is extended at time 4 (since 4 < 6) to 9, and at time 8 (since 8 < 9) to 13. Employee 1 gets expiry 5 at time 2; the event at time 6 arrives after that access ran out, so employee 1 lapses. Employee 2 gets expiry 17 at time 7. The last time point is 8, and employees 0 and 2 are active then.

Example 2

Input:  limits = [3]
        events = [[0, 0], [0, 3], [0, 4]]
Output: 0

The access set at time 0 expires at 3, so it is no longer active at time 3. The event at time 3 cannot extend it: employee 0 lapses, and the event at time 4 is ignored.

Example 3

Input:  limits = [2, 5]
        events = [[0, 0], [1, 0], [1, 2]]
Output: 1

Employee 0 expires at 2, which is not greater than the last time point 2, so it is not counted. Employee 1 is extended at time 2 to 7 and is counted.

Count Employees with Unbroken Access at the Last Event Time

Hints

1. Each employee is always in one of a few situations: never seen, holding access with some expiry, or lapsed for good. Decide what one event does in each situation.
2. Mind the strict comparison: access is active at x only when x < expiry, so an event at exactly the expiry time cannot extend it, and an expiry equal to the last time point is not counted.
3. The log is already in time order, so the last time point is known once every event has been read.

Approach

Simulate the log in one pass. For every employee keep a state (no events yet, active, or lapsed) and the current expiry. For each event [id, t]: if id has lapsed, skip it; if id has no events yet, mark it active with expiry t + limits[id]; if it is active and t < expiry, reset the expiry to t + limits[id]; otherwise (t >= expiry) mark it lapsed. Track t_last as the largest t seen. At the end, count the employees that are active and whose expiry is greater than t_last.

Invariant: after processing any prefix of the log, each employee's state and expiry are exactly what the rules define for that prefix, because every rule depends only on the employee's current state, its current expiry and the event time. Because the log is in non-decreasing time order, once an event finds t >= expiry, every later event for that employee also has t >= expiry, so keeping the employee lapsed and skipping its later events matches the rule that the access is invalid for good. The final count applies the counting rule directly.

Edge cases: an event exactly at the expiry time lapses the employee (activity is strict, x < expiry) and later events never restart it; an expiry equal to t_last is not counted while t_last + 1 is; an employee whose expiry passed without a later event is simply not counted; employees with no events are never counted; several events may share one timestamp; and an expiry can reach 2 * 10^9, so Java and C++ use 64-bit values.

• Time complexity: O(n + m), where n = len(limits) and m = len(events)
• Space complexity: O(n)