Intersect Motion Threshold Periods Across Cameras

Implement common_motion_periods(streams, threshold, end_time). Each camera stream is a nonempty list of [timestamp, intensity] readings sorted by strictly increasing integer timestamp. Intensities are integers from 0 through 1000000, representing values from 0.000000 through 1.000000; threshold uses the same scale.

A reading at timestamp t remains in effect at every integer timestamp from t through one less than the next reading's timestamp. The final reading remains in effect through end_time, inclusive. A camera has no defined intensity before its first reading, so analysis begins at the latest first timestamp among all streams.

Return every maximal inclusive interval [start, end] during which every camera's effective intensity is at least threshold. Intervals must be sorted by start and must not overlap or touch; touching qualifying spans are one maximal interval. With one stream, the function solves the single-camera part.

The discrete time domain, persistence rule, scaling, and explicit horizon are pedagogical assumptions because the source gives timestamp-intensity pairs and inclusive output endpoints without defining interpolation or the last reading's end.

Function Contract

common_motion_periods(streams: list[list[list[int]]], threshold: int, end_time: int) -> list[list[int]]

Constraints

• 1 <= len(streams) <= 1000
• Every stream has at least one reading, and its timestamps are strictly increasing.
• Every reading timestamp is in [0, end_time].
• 0 <= threshold <= 1000000
• 0 <= end_time <= 10^12
• The total number of readings is at most 200000.

Examples

Example 1

Input:
streams = [[[1, 200000], [3, 700000], [6, 800000], [8, 100000]]]
threshold = 600000
end_time = 10
Output: [[3, 7]]

The single camera is above threshold from timestamp 3 through 7; the change at 6 does not break the qualifying period.

Example 2

Input:
streams = [
  [[0, 800000], [5, 300000], [8, 900000]],
  [[2, 700000], [6, 900000], [9, 200000]]
]
threshold = 600000
end_time = 10
Output: [[2, 4], [8, 8]]

Both cameras qualify from 2 through 4 and again only at timestamp 8.

Intersect Motion Threshold Periods Across Cameras

Implement common_motion_periods(streams, threshold, end_time). Each nonempty camera stream contains strictly increasing [timestamp, intensity] integer pairs. An intensity applies at every integer time from its reading through one less than the next reading; the final reading applies through end_time. A camera is undefined before its first reading, so analysis starts at the latest first timestamp. Intensities and threshold use the integer scale 0 through 1,000,000. Return the sorted maximal inclusive [start, end] intervals when every camera's effective intensity is at least threshold. Returned intervals cannot overlap or touch; consecutive qualifying spans form one interval. One stream is the single-camera case.

Hints

1. After the latest first reading, only reading timestamps can change whether all cameras qualify.
2. Process every camera change sharing one timestamp as a group before starting the next span.

Approach

Start at the latest first timestamp and find each camera's effective reading there. Collect every later reading as a timestamped state-change event. Between two event timestamps no camera changes, so the number of cameras meeting the threshold is constant. Sweep grouped timestamps: first append the preceding inclusive integer span if all cameras qualify, then apply every change at that timestamp simultaneously. A helper merges a new qualifying span with the previous one when they touch, so high-to-high changes do not split a maximal interval. After the last event, evaluate through the inclusive end_time.

• Time complexity: O(r log r) time for r total readings, dominated by sorting the change events.
• Space complexity: O(r + c) auxiliary space for the events and c current camera values, besides the returned intervals.