Merge nền trời xa, chia để trị

Question

Tôi đang cố gắng để giải quyết vấn đề đường chân trời nổi tiếng (xem gif):

Input

(1,11,5), (2,6, 7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)

Nên quay lại, các điểm phía sau các tòa nhà khác sẽ biến mất và tọa độ thay đổi trong trục Y phải ở đường chân trời trở về:

(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (23 , 13), (29, 0)

Tôi đang cố gắng làm như vậy bằng cách sử dụng cách tiếp cận phân chia và chinh phục thuật toán để đạt được thời gian chạy O (n lg n), nhưng tôi bị kẹt trên phần hợp nhất.

Mỗi lần tôi nghĩ về điều đó, tôi bị lẫn lộn. Ví dụ: tôi kiểm tra xem đường chân trời nào là đầu tiên, ví dụ: trong đó có tọa độ x thấp hơn, sau đó tôi thêm + điểm cao của nó vào đường chân trời mới của tôi. Nhưng sau đó tôi gặp một đường chân trời đằng sau hai đường chân trời khác, làm sao tôi có thể phát hiện 'va chạm' này?

Trước tiên, tôi có kiểm tra xem các đường chân trời có bất kỳ trùng lặp nào hay không bằng cách kiểm tra xem còn lại.x2 < right.x1 không? Nhưng sau đó tôi nghĩ tôi nên kiểm tra cái gì trước? Chồng chéo ưu tiên trên trục x và mọi thứ biến thành một mớ hỗn độn trứng gà lớn.

Có lẽ tôi đang suy nghĩ quá phức tạp? Những gì tôi cần là tập hợp các tọa độ y cao nhất, tại mọi giao lộ, tôi có nên tiếp cận nó như thế này không?

Answer 1

Tôi nghĩ rằng đây phải là một cách tiếp cận đó là dễ dàng hơn để quấn quanh đầu của một người xung quanh:

• Chia x-tọa độ vào bắt đầu và kết thúc các đối tượng cho mỗi hình chữ nhật, như sau:

  rect(x1, y, x2) -> (x1, y, "start", reference to rect), 
          (x2, y, "finish", reference to rect) 
  

  Vì vậy, một cái gì đó như:

  class MyStruct 
  { 
      Rectangle rect; 
      int x, y; 
      bool isStart; 
  } 
  

• Sắp xếp các đối tượng này theo toạ độ x (O(n log n))
• Tạo một nhóm hình chữ nhật (vô căn) trống (sẽ được sắp xếp theo tọa độ y, ví dụ:một BST)
• Vòng qua các đối tượng này (theo thứ tự bây giờ sắp xếp) (O(n))
  • Bất cứ khi nào một sự khởi đầu được gặp
    • Thêm hình chữ nhật với tập hợp các hình chữ nhật (O(log n))
    • Nếu đó là hình chữ nhật cao nhất mới, thêm rằng điểm đầu đến đầu ra (O(1))
  • Bất cứ khi nào một kết thúc được gặp
    • Di chuyển hình chữ nhật từ tập các hình chữ nhật (O(log n))
    • Nếu đó là hình chữ nhật cao nhất, tìm ra hình chữ nhật cao nhất tiếp theo trong tập và thêm điểm (current.finishX, new.y) đến đầu ra (O(1)) (nếu các thiết lập là trống rỗng, thêm (current.finishX, 0) để đầu ra thay vì)

Vì vậy O(n log n).

Answer 2

Điều này có thể đạt được bằng cách sửa đổi thuật toán cho sắp xếp hợp nhất. Thuật toán cho đường chân trời trông giống như:

ConstructSkyLine

ConstructSkyLine(List B) --------------- O(nlogn) 
    { 
     If(B.size() == 1) 
     { 
      List skyLineList = new List(); 
      SKYLINE = new SKYLINE(B.XL, B.XR, B.H); 
      skyLineList.add(SKYLINE); 
      Return skyLineList; 
     } 
     B1, B2 <-- Split(B); 
     List S1 <-- ConstructSkyLine(B1); 
     List S2 <-- ConstructSkyLine(B2); 
     List S <-- MergeSkyline(S1, S2); 
     Return S; 
    } 

MergeSkyline

MergeSkyline(List S1, List S2) --------------- O(n) 
    { 
     List< SKYLINEENTRY> skylineEntryList = new ArrayList<SKYLINEENTRY>(); 
     while (S1.isEmpty() && S2.isEmpty())--------------- O(n) 
     { 
      S1Item <-- S1.get(0); 
      S2Item <-- S2.get(0); 
      If (S1Item.XL < S2Item.XL) 
      { 
      Merge(S1, S2, skylineEntryList); --------------- O(n) 
      } 
      Else 
      { 
      Merge(S2, S1, skylineEntryList); --------------- O(n) 
      } 
     } 

     If(!S1.isEmpty()) 
     { 
      skylineEntryList.add(S1); 
     } 

     If(!S2.isEmpty()) 
     { 
      skylineEntryList.add(S2); 
     } 
     Retrun skylineEntryList; 
     } 

Merge

Merge(S1, S2, skylineEntryList) --------------- O(n) 
    { 
    SKYLINEENTRY <-- null; 
    S1Item <-- S1.get(0); 
    S2Item <-- S2.get(0); 
    SKYLINEENTRY.XL = S1Item.XL; 
    If(S1Item.XR > S2Item.XL) // means over lap 
    { 
     If(S1Item.H > S2Item.H) // S1 is higher. 
     { 
      SKYLINEENTRY.XR = S1Item.XR; 
      SKYLINEENTRY.H = S1Item.H; 
      S1.remove(S1Item); --------------- O(n) 
      skylineEntryList.add(SKYLINEENTRY); 
      if(S2Item.XR < S1Item.XR) // full overlap 
      { 
       S2.remove(S2Item); --------------- O(n) 
      } 
      Else // partial overlap 
      { 
       S2Item.XL <-- S1Item.XR; 
      }    
     } 
     Else //S2 is higher 
     { 
      SKYLINEENTRY.XR = S2Item.XL; 
      SKYLINEENTRY.H = S1Item.H; 
      if(S2Item.XR < S1Item.XR) // full overlap with S2 
      { 
       S1Item.XL = S2Item.XR; 
      } 
      Else // partial overlap 
      { 
       S1.remove(S1Item); --------------- O(n) 
      }  
      skylineEntryList.add(SKYLINEENTRY); 
     } 
    } 
    Else // no overlap 
    { 
     SKYLINEENTRY.XR = S1Item.XR; 
     SKYLINEENTRY.H = S1Item.H; 
     S1.remove(S1Item); --------------- O(n) 
     skylineEntryList.add(SKYLINEENTRY); 
    } 
    }