- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a list of intervals, where intervals[i] has a pair (left_i, right_i) represents the ith interval starting at left_i and ending at right_i (both inclusive). We also have another array called queries. The answer to the jth query is the size of the smallest interval i such that left_i <= queries[j] <= right_i. If we cannot find such interval, then return -1. We have to find an array containing the answers to the queries.

So, if the input is like intervals = [[2,5],[3,5],[4,7],[5,5]] queries = [3,4,5,6], then the output will be [3, 3, 1, 4], because The queries are processed as follows −

for query = 3: The interval [3,5] is the smallest one holding 3. so, 5 - 3 + 1 = 3.

for query = 4: The interval [3,5] is the smallest one holding 4. so, 5 - 3 + 1 = 3.

for query = 5: The interval [5,5] is the smallest one holding 5. so, 5 - 5 + 1 = 1.

for query = 6: The interval [4,7] is the smallest one holding 6. so, 7 - 4 + 1 = 4.

To solve this, we will follow these steps −

intervals := sort the list intervals in reverse order

h := a new list

res := a new map

for each q in the sorted list of queries, do

while intervals is not empty and end time of last interval <= q, do

(i, j) := last interval from intervals, and remove it

if j >= q, then

insert pair (j-i+1, j) into heap h

while h is not empty and end time of top most interval in h < q, do

delete top element from h

res[q] := start time of top most interval of h if h is not empty otherwise -1

return a list of res[q] for all q in queries

Let us see the following implementation to get better understanding

import heapq def solve(intervals, queries): intervals = sorted(intervals)[::-1] h = [] res = {} for q in sorted(queries): while intervals and intervals[-1][0] <= q: i, j = intervals.pop() if j >= q: heapq.heappush(h, [j - i + 1, j]) while h and h[0][1] < q: heapq.heappop(h) res[q] = h[0][0] if h else -1 return [res[q] for q in queries] intervals = [[2,5],[3,5],[4,7],[5,5]] queries = [3,4,5,6] print(solve(intervals, queries))

[[2,5],[3,5],[4,7],[5,5]], [3,4,5,6]

[3, 3, 1, 4]

- Related Questions & Answers
- Program to find one minimum possible interval to insert into an interval list in Python
- Program to find maximum XOR for each query in Python
- Program to find minimum cost to connect each Cartesian coordinates in C++
- Program to find minimum number of operations to move all balls to each box in Python
- Program to find intervals by merging target interval in Python
- Program to find minimum jumps to reach home in Python
- Program to find minimum cost to merge stones in Python
- Program to find path with minimum effort in Python
- Program to find minimum absolute sum difference in Python
- Python program to find occurrence to each character in given string
- Program to count number of similar substrings for each query in Python
- Program to find minimum time to complete all tasks in python
- Program to find minimum cost to connect all points in Python
- Program to find minimum moves to make array complementary in Python
- Program to find minimum deletions to make string balanced in Python

Advertisements