各クエリを含める最小間隔 ---パイセップ--- 「各クエリを含める最小間隔」問題の詳細なガイドと __PYTERM_0__ 実装。 ---パイセップ--- 2D 整数配列の間隔が与えられます。ここで、intervals[i] = [left_i, right_i] は、left_i で始まり right_i で終わる i 番目の間隔を表します (両端を含む)。間隔のサイズは、right_i - left_i + 1 として定義されます。また、整数配列クエリも提供されます。 j 番目のクエリに対する答えは、left_i <= queries[j] <= right_i となる最小間隔 i のサイズです。そのような間隔が存在しない場合、答えは -1 です。 クエリに対する回答を含む配列を返します。 関数 __PYCODE_0__ を作成します。 ---パイセップ--- トップ150インタビュー ---パイセップ--- 間隔 ---パイセップ--- 「各クエリを含める最小間隔」問題は、「間隔」セクションの重要な課題です。 ---パイセップ--- この実装は、__PYTERM_0__ の簡単なレベルのロジックに焦点を当てています。 ---パイセップ--- 当社は、提供するソリューションにおいて技術的な正確さとコードの読みやすさを優先します。 ---パイセップ--- アルゴリズム工学 ---パイセップ--- 競技プログラミング ---パイセップ--- 技術的評価 ---パイセップ--- 各クエリを含める最小間隔のロジック フローを視覚化します。 ---パイセップ--- 「各クエリを含める最小間隔」の問題文を注意深く読んでください。 ---パイセップ--- 単純な反復ソリューションの草案を作成します。 ---パイセップ--- 冗長な計算を探します。 ---パイセップ--- プロセスを高速化するには、ハッシュまたはソートを使用します。 ---パイセップ--- 実稼働標準に合わせてコードをクリーンアップします。 ---パイセップ--- 空の入力構造体 ---パイセップ--- 単一要素入力 ---パイセップ--- 大きな数値限界 ---パイセップ--- インターバルアプローチのロジックを説明してください。 ---パイセップ--- null または空の入力などの特殊なケースについて説明します。 ---パイセップ--- 標準間隔の問題プロパティが適用されます。 ---パイセップ--- セットやヒープなどの間隔固有のデータ構造の使用を検討してください。 ---パイセップ--- 単一の数字 ---パイセップ--- 「単一数値」問題の詳細なガイドと __PYTERM_0__ の実装。 ---パイセップ--- 整数 num の空でない配列を指定すると、1 つを除いてすべての要素が 2 回現れます。その 1 つを見つけてください。 実行時の複雑さが線形になるソリューションを実装し、一定の追加スペースのみを使用する必要があります。 関数 __PYCODE_0__ を作成します。 ---パイセップ--- トップ150インタビュー ---パイセップ--- ビット操作 ---パイセップ--- 「単一の数値」問題は、ビット操作セクションの重要な課題です。 ---パイセップ--- この実装は、__PYTERM_0__ の簡単なレベルのロジックに焦点を当てています。 ---パイセップ--- 当社は、提供するソリューションにおいて技術的な正確さとコードの読みやすさを優先します。 ---パイセップ--- アルゴリズム工学 ---パイセップ--- 競技プログラミング ---パイセップ--- 技術的評価 ---パイセップ--- Single Number のロジック フローを視覚化します。 ---パイセップ--- Single Number の問題文を注意深く読んでください。 ---パイセップ--- 単純な反復ソリューションの草案を作成します。 ---パイセップ--- 冗長な計算を探します。 ---パイセップ--- プロセスを高速化するには、ハッシュまたはソートを使用します。
Detailed guide and Python implementation for the 'Minimum Interval to Include Each Query' problem.
1. 学ぶ
The 'Minimum Interval to Include Each Query' problem is a key challenge in the Intervals section.
This implementation focuses on easy-level logic in Python.
We prioritize technical accuracy and code readability in our provided solutions.
2. Real-World Applications
3. Visual Intuition
Visualizing the logic flow for Minimum Interval to Include Each Query.
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
Read the problem statement for Minimum Interval to Include Each Query carefully.
2. Formulate brute force
Draft a simple iterative solution.
3. Identify inefficiency
Look for redundant calculations.
4. Optimize search path
Use hashing or sorting to speed up the process.
5. Final Implementation
Clean up the code for production standards.
問題提起
You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] describes the ith interval starting at left_i and ending at right_i (inclusive). The size of an interval is defined as right_i - left_i + 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 left_i <= queries[j] <= right_i. If no such interval exists, the answer is -1.
Return an array containing the answers to the queries.
Write a function minInterval(intervals: List[List[int]], queries: List[int]) -> List[int].
- •1 <= len(intervals) <= 10^5
- •1 <= len(queries) <= 10^5
- •intervals[i].length == 2
- •1 <= left_i <= right_i <= 10^7
- •1 <= queries[j] <= 10^7
例
intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
[3,3,1,4]
Smallest interval containing 2 is [2,4] (size 3). For 3 is [2,4] (size 3). For 4 is [4,4] (size 1). For 5 is [3,6] (size 4).
intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
[2,-1,4,6]
For 2: [2,3] (size 2). For 19: none (-1). For 5: [2,5] (size 4). For 22: [20,25] (size 6).
Need a Hint?
Edge Cases to Watch
- Empty input structures
- Single element inputs
- Large numerical bounds
解決する準備はできましたか?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
インタビューの洞察とバリエーション
複雑さの分析の内訳
なぜ時間がかかるのか: Directly evaluates all possibilities.
なぜ宇宙なのか: Uses standard local memory.
なぜ時間がかかるのか: Optimized paths reduce total operations.
なぜ宇宙なのか: May trade memory for speed.
最適化されたソリューションの Python コード
最適化されたソリューションの Python コード
import heapq
def min_interval_opt(intervals, queries):
intervals.sort()
minHeap = []; res, i = {}, 0
for q in sorted(queries):
while i < len(intervals) and intervals[i][0] <= q:
l, r = intervals[i]
heapq.heappush(minHeap, (r - l + 1, r))
i += 1
while minHeap and minHeap[0][1] < q: heapq.heappop(minHeap)
res[q] = minHeap[0][0] if minHeap else -1
return [res[q] for q in queries]ブルート フォース コード (スポイラーガード付き)
ブルート フォース コード (スポイラーガード付き)
def min_interval_brute(intervals, queries):
res = []
for q in queries:
min_len = float("inf")
for i in intervals:
if i[0] <= q <= i[1]:
min_len = min(min_len, i[1] - i[0] + 1)
res.append(min_len if min_len != float("inf") else -1)
return resAlgorithm Pattern Checklist
When dealing with Intervals data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
Key Revision Notes
Standard Intervals problem properties apply.
関連する質問
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
推奨される Python リソース
関連するインタラクティブなチュートリアル、チートシート、コード比較で知識を深めてください。
Python ジェネレーター
Python ジェネレーターと yield ステートメントを使用して、最小限のメモリ フットプリントで巨大なデータセットを処理する方法を学びます。ジェネレーター式をマスターします。
Python で文字列を Int に変換する方法
Python で int() 関数を使用して文字列を整数に変換する方法を学びます。エラーを安全に処理し、数値を 2 進数、8 進数、または 16 進数から変換します。
Python オペレーターのチートシート
Python の算術演算子、比較演算子、論理演算子、ビット演算子、代入演算子、恒等演算子をマスターします。
Python デコレータとデコレータ デザイン パターン: 主な違い
Python デコレータと従来のデコレータ デザイン パターンを比較します。定義時の関数ラッピングと、実行可能なコードを使用した実行時の動的オブジェクト構成の違いを理解します。