Interval Tree Overlap Query

Problem

Find the intervals that overlap a query range.

intervals is a list of [start, end] inclusive intervals and query is [ql, qr]. Two intervals overlap when lo is at most qr and hi is at least ql.

Return the sorted indices of the overlapping intervals.

Hint

Two inclusive intervals overlap unless one ends before the other starts.

case 1

in: [[[1,3],[5,7],[6,10]],[2,6]]

expected: [0,1,2]

case 2

in: [[[1,2]],[3,4]]

expected: []

case 3

in: [[],[0,1]]

expected: []

case 4

in: [[[1,1],[2,2]],[1,2]]

expected: [0,1]

Starter codePython

def interval_overlap_query(intervals, query):
    # Your code here
    pass

4 test cases · run your code against them in the editor