這不是一個家庭作業問題。它是一個面試問題。我無法爲這個問題提出好的解決方案。算法 - 查找覆蓋給定矩形區域的矩形的數量
問題：
鑑於平行於座標軸的n×n個（左下（0,0），右上（N，N））網格和正矩形各邊。以（x1，y1）（x1'，y1'）...（xn，yn）（xn'，yn'）的形式提供n個矩形的左下角和右上角座標。有M個查詢要求用座標（a，b）（c，d）覆蓋矩形的矩形數量。我如何以有效的方式解決問題？是否有預先計算所有座標位置的方法，以便我可以返回O（1）中的答案。
限制條件： = N < = 1000
它是簡單的創建，在爲O（n^4）的空間和爲O（n^5）的時候，一個數據結構，可提供O（1）查找。如果M超過O（n^2），這可能是值得的。在O（n^2）空間和O（n^3）時間內創建提供O（n）時間查找的數據結構也很簡單。如果M是O（n^2），那可能是一個更好的折衷;即在O（n）每個O（n）查找O（n^3）預計算時間和O（n^3）時間。
對於預計算，通過列表n進行n次排列。令L_pq表示n乘n格的單元p，q的列表。每個列表最多包含n個矩形，列表全部按同一關係排序（即，如果Ri < Rj在一個列表中，Ri < Rj在每個列表中都存在）。這組列表需要花費時間O（n^3）來計算，或者作爲「對於n×2個單元中的每個C，對於n個矩形中的每個R，如果R中的C將R加到L_C」或者對於每個R在n個矩形中，對於R中的每個單元C，將R添加到L_C「。給定查詢（a，b，c，d），在時間O（n）中計數列表L_ab和L_cd的交集的大小。對於O（1）查找，首先執行上述預計算，然後對每個a，b，對於每個c>a和d<b，執行上述O（n）查詢並將結果保存在P [a，b，c， d]其中P是一個相當大的整數數組。
很可能爲O（n^3）或也許爲O（n^2·log n）的使用任一segment trees，range trees，或interval trees其可以在O做查詢（log n）的預計算時間的方法存在。
還有很多需要澄清的地方。你在尋找什麼？ （你沒有在問題中說!!）「M查詢」是什麼意思？如果我指定的區域只包含矩形的一部分，會發生什麼？許多問題需要首先提出。 – riwalk
事實上，你要求一個O（1）的解決方案讓我對n個矩形感到困惑。如果您必須使用所有n個矩形來計算您的解決方案，那麼最好使它成爲O（n）解決方案。 – 0xFE
-1不提供細節。我懷疑你的問題是你對這個問題的掌握很差，在這種情況下，答案是無關緊要的 - 如果沒有正確理解面試官的要求，你永遠無法得出正確的答案。 – riwalk