最小の矩形の中に点を見つけます。 O（n）とが、さらなる

Question

インタビューの質問最適化：長方形の

を考えると数十億、任意の点P（x、y）は

に答えを達成するための簡単な方法がありますが重複最小面積の長方形を見つけることを各矩形を順番に処理することによってO（n）時間がかかるが、それをさらに最適化するために、多数の矩形配列を提供する。

私の最善のアプローチは、各矩形をチェックし、その点が内側かどうかを確認し、面積を計算し、現在の最小面積と比較することです。これは1回のパスで行うことができます。私はすべての長方形をチェックする必要がない他の方法を考え出すことはできません

Answer 1

は、その後、R-treeデータ構造は、おそらくあなたは完全な質問を言っていないすべての矩形

Answer 2

もちろん、すべての四角形を少なくとも1回は処理する必要があります。しかし、最初のパスを賢明に使うと、後で複数の検索を高速化できます。

K-d treeまたはQuadtreeに長方形を挿入します。あなたは多くのポイントクエリと同じ長方形のセットを使用する場合は

Answer 3

をチェックせずに、与えられた点が含まれているものを四角形知ることができます。今のところどのように立っているので、あなたのソリューションは最適です。

各矩形を通過して実際にポイントをカバーしているかどうかをチェックし、そのエリアを計算する必要があるかどうかは関係ありません。 に1つの質問と答える必要があるため、何らかの方法で前処理する必要はありません。

前処理は、今後多くの同様の質問に回答する必要がある場合にのみ意味を持ちます。