Katkat
Back

Find Windows Containing a Target

RobloxMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to efficiently filter and identify intervals within a collection that satisfy specific containment constraints using two-pointer or sliding window techniques.

Problem Statement

You are given a list of intervals windows, where each interval is represented as [start, end]. You are also given a target interval [target_start, target_end].

Your task is to return a list of the indices of all windows that are entirely contained within the target interval. A window [s, e] is contained within [target_start, target_end] if and only if `target_start list[int]:


### Constraints
- `1 <= len(windows) <= 10^5`
- `windows[i][0] <= windows[i][1]`
- All interval values are integers.

### Examples

**Example 1:**
Input: `windows = [[1, 3], [2, 5], [6, 7], [4, 4]]`, `target = [1, 5]`
Output: `[0, 1, 3]`
Explanation: 
- `[1, 3]` is within `[1, 5]` (index 0).
- `[2, 5]` is within `[1, 5]` (index 1).
- `[6, 7]` is outside.
- `[4, 4]` is within `[1, 5]` (index 3).

**Example 2:**
Input: `windows = [[10, 20], [1, 5]]`, `target = [2, 8]`
Output: `[]`

### Edge Cases
- Empty `windows` list.
- Windows where `start == end`.
- The target interval is exactly equal to one of the windows.

Hints

Hint 1

Iterate through the `windows` list while keeping track of the original index of each interval.

Hint 2

For each window `[s, e]`, compare the start and end values against the `target_start` and `target_end` constants.

Hint 3

Ensure the logic correctly handles inclusive boundaries by using `=` comparison operators.

Follow-up questions

  • How would you optimize the solution if you needed to perform this check repeatedly for millions of queries against the same set of windows?
  • If the input windows were already sorted by their start times, how could you use binary search to narrow down the search space?
  • How would your approach change if the requirement shifted from identifying 'contained' windows to identifying windows that have any overlap with the target?