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.