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 ```python 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** ```text 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** ```text 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** ```text Input: timestamps = [], queries = [[0, 10]] Output: [[-1, -1]] ``` An empty log has no entries in any window.