Count Employees With Unbroken Renewable Access at the Last Timestamp
Company: IBM
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: A simulation problem about an access system where each employee's access lasts a fixed duration after every setting and can be extended only while it is still active. It asks how many employees hold valid access at the last timestamp, testing exact expiry boundaries, permanent lapses and per-employee state.
Read the full IBM Software Engineer interview experience this question came from
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`.
### 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.
Return that count as an integer.
### Example 1
```text
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
```text
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.
### 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 `t + limits[id]` can reach `2 * 10^9`; use 64-bit integers for expiry arithmetic (`long` in Java, `long long` in C++).
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 t + limits[id] can reach 2 * 10^9; use 64-bit integers for expiry arithmetic (long in Java, long long in C++).
Examples
Input: ([5, 3, 10], [[0, 1], [1, 2], [0, 4], [1, 6], [2, 7], [0, 8]])
Expected Output: 2
Explanation: Source example 1: employee 0 is extended to 9 and then 13, employee 1 lapses at time 6, and employees 0 and 2 are active at t_last = 8.
Input: ([3], [[0, 0], [0, 3], [0, 4]])
Expected Output: 0
Explanation: Source example 2: the event at exactly the expiry time 3 lapses employee 0, and the event at time 4 is ignored.
Hints
- 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.
- 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.
- The log is already in time order, so the last time point is known once every event has been read.