Count Distinct Active Pins per Time Segment from Overlapping Interaction Logs

You are given interaction logs for pins. Each log [pin_id, start, end] means that some user was interacting with pin pin_id during the half-open time interval [start, end). For every elementary time segment defined by the logs, report how many distinct pins were being interacted with.

The same pin can appear in many logs, because several users can interact with it, and its intervals can overlap. A pin counts once in a segment, no matter how many of its intervals cover that segment.

This is the last step of a three-step progression. The first version limited timestamps to a 60-second window (0 to 59) and assumed each pin appeared in at most one log. The second version removed the window limit, allowing arbitrary timestamps. This version also removes the one-log-per-pin assumption.

Function Signature

def distinct_active_pins(logs: list[list[int]]) -> list[list[int]]:
    ...

Rules

• Let T be the sorted list of distinct values that appear as a start or an end in any log.
• For each pair of consecutive values T[i] < T[i + 1], output one row [T[i], T[i + 1], count]. Here count is the number of distinct pin_id values that have at least one log with start <= T[i] and T[i + 1] <= end.
• Output the rows in ascending order of their start time. Output a row for every consecutive pair, including rows whose count is 0 and neighboring rows with equal counts. Do not merge rows.
• Intervals are half-open. A log that ends at time t and another that starts at time t do not overlap.
• If logs is empty, return an empty list.

Constraints

• 0 <= len(logs) <= 100000
• 0 <= pin_id <= 10^9
• 0 <= start < end <= 10^12
• Timestamps can exceed 2^31 - 1, so use 64-bit integers.
• Logs are unsorted, and some may be exact duplicates of each other.

Examples

Input: logs = [[7, 1, 5], [7, 3, 8], [9, 4, 6]]

Output: [[1, 3, 1], [3, 4, 1], [4, 5, 2], [5, 6, 2], [6, 8, 1]]

During [3, 5), two of pin 7's logs overlap, but pin 7 is counted only once.

Input: logs = [[1, 0, 2], [2, 5, 6]]

Output: [[0, 2, 1], [2, 5, 0], [5, 6, 1]]

Distinct Active Pins Per Elementary Time Segment

You are given interaction logs for pins. Each log is a triple [pin_id, start, end] meaning that some user interacted with pin pin_id during the half-open time interval [start, end). The same pin can appear in many logs, because several users can interact with it, and its intervals can overlap or even be exact duplicates. A pin counts once in a segment, no matter how many of its intervals cover that segment.

For every elementary time segment defined by the logs, report how many distinct pins were being interacted with:

• Let T be the sorted list of the distinct values that appear as a start or an end in any log.
• For each pair of consecutive values T[i] < T[i + 1], output one row [T[i], T[i + 1], count], where count is the number of distinct pin_id values that have at least one log with start <= T[i] and T[i + 1] <= end.
• Output the rows in ascending order of their start time. Output a row for every consecutive pair, including rows whose count is 0 and neighbouring rows with equal counts. Do not merge rows.
• Intervals are half-open: a log that ends at time t and another that starts at time t do not overlap.
• If logs is empty, return an empty list.

Timestamps can exceed 2^31 - 1 (they go up to 10^12), so use 64-bit integers: long in Java and long long in C++.

Example 1

Input: logs = [[7, 1, 5], [7, 3, 8], [9, 4, 6]]

Output: [[1, 3, 1], [3, 4, 1], [4, 5, 2], [5, 6, 2], [6, 8, 1]]

During [3, 5), two of pin 7's logs overlap, but pin 7 is counted only once.

Example 2

Input: logs = [[1, 0, 2], [2, 5, 6]]

Output: [[0, 2, 1], [2, 5, 0], [5, 6, 1]]

The segment [2, 5) has no active pin, but its row is still emitted with count 0.

Hints

1. Every row boundary is already present in the input: only values that appear as some start or some end can begin or end a segment, so the full set of candidate boundaries is fixed before you count anything.
2. The intervals are half-open, so a timestamp t that ends one log and starts another belongs only to the segment beginning at t; settle what happens at t before you record the row that starts there.
3. A pin may appear in several logs that overlap, so 'one of this pin's logs just ended' is not the same as 'this pin is no longer active'.

Approach

Algorithm: collect every start and every end as a candidate boundary, deduplicate and sort them into the list T, then sweep the boundaries left to right maintaining a multiplicity map live from pin_id to the number of that pin's logs currently covering the segment about to begin, plus a running counter distinct of the pins whose multiplicity is positive. At each boundary t, first apply every log that ends at t (decrementing that pin's multiplicity, and decrementing distinct only when the multiplicity falls from 1 to 0), then apply every log that starts at t (incrementing the multiplicity, and incrementing distinct only when it rises from 0 to 1). After both groups are applied, the state describes exactly the segment [T[i], T[i+1]), so append the row [T[i], T[i+1], distinct]; the last boundary starts no segment and emits no row.

Invariant: immediately before emitting the row for [T[i], T[i+1]), live[p] equals the number of logs of pin p with start <= T[i] < end, and distinct equals the number of pins with live[p] > 0.

Correctness: no log boundary lies strictly inside a segment, because T contains every start and end, so a log either covers a whole segment or is disjoint from it. A log [p, s, e) covers [T[i], T[i+1]) exactly when s <= T[i] and T[i+1] <= e, which because of the half-open convention is equivalent to s <= T[i] < e - that is, the log's start event has been applied at or before T[i] and its end event has not. The multiplicity map is exactly that difference of applied events, so distinct is the number of pins with at least one covering log, which is the required count. Processing ends before starts at the same boundary is the half-open rule: a log ending at t no longer covers [t, ...), while a log starting at t does. Rows are emitted once per consecutive pair in boundary order, so they are ascending by start time and never merged, and zero-count rows appear naturally for gaps.

Edge cases: empty logs returns []; a single log yields exactly one row; exact duplicate logs and overlapping logs of one pin raise that pin's multiplicity above 1 and still contribute 1 to distinct; touching intervals [a, b) and [b, c) never share a segment; pin_id 0 and start 0 are valid; timestamps up to 10^12 exceed 32-bit range, so Java uses long and C++ uses long long (JavaScript numbers hold these exactly, being well under 2^53).

• Time complexity: O(n log n)
• Space complexity: O(n)