Find Inclusive Index Ranges for Time-Window Queries on Timestamp-Sorted Logs

A service stores the timestamps of its log entries in an array sorted in non-decreasing order, so entry i has timestamp timestamps[i]. The same log is queried many times, and each query asks which entries fall inside a time window [start, end].

For each query, return the inclusive index range [first, last] of the log entries whose timestamps lie inside the window. Several entries may share the same timestamp, both ends of the window are inclusive, and the window may begin before the earliest entry or end after the latest one.

Function Signature

def log_window_ranges(timestamps: list[int], queries: list[list[int]]) -> list[list[int]]:

Each query is a pair [start, end].

Rules

• Entry i is in the window when start <= timestamps[i] <= end.
• For each query, first is the smallest index and last is the largest index of an entry in the window. Because timestamps is sorted, every index from first to last is in the window.
• If no entry falls in the window, the answer for that query is [-1, -1].
• start and end need not be timestamps that occur in timestamps, and either may lie before the first entry or after the last one.
• Return one [first, last] pair per query, in the same order as queries.

Constraints

• 0 <= len(timestamps) <= 10^5
• 1 <= len(queries) <= 10^5
• timestamps is sorted in non-decreasing order; values may repeat.
• 0 <= timestamps[i] <= 10^9
• 0 <= start <= end <= 2 * 10^9 for every query; all values fit in a 32-bit signed integer.
• Answer each query in $O(\log n)$ time, where $n$ is len(timestamps); scanning the log for every query is too slow at these limits.

Examples

Example 1

Input: timestamps = [1, 3, 3, 5, 8], queries = [[3, 5], [0, 100], [6, 7]]
Output: [[1, 3], [0, 4], [-1, -1]]

For [3, 5], both entries at timestamp 3 (indices 1 and 2) and the entry at timestamp 5 (index 3) are inside the inclusive window. [0, 100] begins before the first entry and ends after the last one, so it covers the whole log. No entry has a timestamp from 6 to 7.

Example 2

Input: timestamps = [2, 2, 2, 4, 4, 9], queries = [[2, 2], [3, 4], [4, 20], [0, 1], [10, 15]]
Output: [[0, 2], [3, 4], [3, 5], [-1, -1], [-1, -1]]

[2, 2] returns the whole run of entries at timestamp 2. [3, 4] starts at a timestamp that does not occur in the log. [4, 20] ends after the latest entry. [0, 1] lies entirely before the earliest entry and [10, 15] entirely after the latest, so both are empty.

Example 3

Input: timestamps = [], queries = [[0, 10]]
Output: [[-1, -1]]

An empty log has no entries in any window.