bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
HardIntervalsLC 1851

Minimum Interval to Include Each Query

You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1. You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1. Return an array containing the answers to the queries.

Hints
  • 1.Think about what data structure fits Minimum Interval to Include Each Query
  • 2.Consider the brute force complexity and how to optimize
  • 3.Can you trade space for time?
LeetCodeNeetCode