Count Distinct Active Pins per Time Segment from Overlapping Interaction Logs

Problem Statement

At Pinterest, user activity on pins is logged as interaction records. You are given a list of logs where each record is represented as (pin_id, start_time, end_time). This indicates that a user interacted with pin_id during the half-open interval [start_time, end_time).

A single pin can have multiple overlapping or disjoint interactions from different users. A pin is considered active at time t if there is at least one interaction for that pin such that start_time <= t < end_time.

Your task is to compute the number of distinct active pins over time. Return a list of non-overlapping, contiguous time segments (seg_start, seg_end, distinct_count) covering all times where distinct_count > 0.

If two consecutive segments (t1, t2, c1) and (t2, t3, c2) have the same pin count (c1 == c2), they should be merged into a single segment (t1, t3, c1).

Function Signature

def count_active_pins(interactions: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:
    pass

Input Format

• interactions: A list of tuples (pin_id, start_time, end_time) where pin_id, start_time, and end_time are integers.

Output Format

• Return a list of tuples (seg_start, seg_end, distinct_count) sorted by seg_start in ascending order, where distinct_count > 0 and adjacent segments with the same count are merged.

Constraints

• 0 <= len(interactions) <= 10^5
• 1 <= pin_id <= 10^9
• -10^9 <= start_time < end_time <= 10^9

Examples

Example 1

interactions = [
    (1, 10, 20),
    (1, 15, 25),
    (2, 12, 18),
]

Output:

[
    (10, 12, 1),
    (12, 18, 2),
    (18, 25, 1)
]

Explanation:

• Pin 1 is active on [10, 20) and [15, 25), which merges to [10, 25).
• Pin 2 is active on [12, 18).
• Distinct active pins:
  • [10, 12): Pin 1 (count = 1)
  • [12, 18): Pins 1 and 2 (count = 2)
  • [18, 25): Pin 1 (count = 1)

Example 2

interactions = [
    (1, 1, 5),
    (2, 3, 7),
    (3, 5, 9)
]

Output:

[
    (1, 3, 1),
    (3, 7, 2),
    (7, 9, 1)
]

Explanation:

• At t = 5, Pin 1 becomes inactive and Pin 3 becomes active. The active count remains 2 from [3, 5) to [5, 7), so the segment [3, 7) is merged with count 2.

Edge Cases to Consider

• Empty input logs (interactions = []).
• Multiple non-overlapping intervals for the same pin.
• Exact boundary alignments (e.g., one interaction ends at t while another starts at t).