放置塊並計算最高塔的高度

給出k個塊的系列（k1，k2，...，ki）。每個塊從位置ai開始，結束於位置bi，其高度爲1.塊連續放置。如果該塊與另一塊重疊，則將其附着在其頂部。我的任務是計算最高的街區。我創建了一個算法，其時間複雜度約爲O（n^2），但我知道使用skiplist有更快的解決方案。放置塊並計算最高塔的高度

#include <iostream> 

struct Brick 
{ 
    int begin; 
    int end; 
    int height = 1; 
}; 

bool DoOverlap(Brick a, Brick b) 
{ 
    return (a.end > b.begin && a.begin < b.end) 
} 

int theHighest(Brick bricks[], int n) 
{ 
    int height = 1; 

    for (size_t i = 1; i < n; i++) 
    { 
     for (size_t j = 0; j < i; j++) 
     { 
      if (bricks[i].height <= bricks[j].height && DoOverlap(bricks[i], bricks[j])) 
      { 
       bricks[i].height = bricks[j].height + 1; 

       if (bricks[i].height > height) 
        height = bricks[i].height; 
      } 
     } 
    } 

    return height; 
}

That's an example drawing of created construction.

來源

2017-08-30 PatrykTraveler

你的問題是什麼？你的代碼在哪裏？ –

你可以分享你創建的算法嗎？ – neuhaus

ai，bi的範圍是多少？ – sourabh1024

下面是一個簡單的解決方案（沒有跳過列表）：

通過塊創建一個數組heights

迭代。

每個塊

檢查高度陣列用於當前塊佔據由遍歷它們的位置中的現有條目。確定它們的最大值。
將當前塊的高度數組中的值增加到上一步中確定的最大值+1。
保持在掃描過程中建立的最高塔的分數。

來源

2017-08-30 19:32:55 neuhaus

我不確定你是否正確理解了我。如果在將塊放在另一個塊上時確定每個塊的高度，那麼創建一個高度數組有什麼意義？ – PatrykTraveler

不必爲每塊磚塊都穿過所有其他磚塊 – neuhaus

如果可能的位置很稀疏，請使用散列而不是數組。 – neuhaus

此問題與圖遍歷是同構的。每個區間（塊）都是圖形的一個節點。兩個塊通過邊緣連接，如果它們的區間重疊（堆疊的可能性）。您給出的示例具有圖形邊緣

1 2 
1 3 
2 3 
2 5 
and node 4 has no edges

您的最高堆棧同構於圖中最長的無週期路徑。這個問題有衆所周知的解決方案。

順便說一句，我不認爲你的n^2算法適用於所有排序的塊。嘗試一組六個塊，每個塊重疊一次，如{2，4，6，8，10，12}中的n的區間[n，n + 3]。將這些塊的所有排列都送到您的算法中，並查看它是否每個都有6的高度。

複雜

我認爲最高的複雜性很可能被分揀的時間間隔，加快標記邊緣。排序將爲O（n log n）。添加邊是O（n d）其中d是圖的平均度（並且n * d是邊的數量）。

我並沒有牢記graph traversal algorithm，但我預計它是O（d log n）。

來源

2017-08-30 20:10:33 Prune

這真的很有趣的解決方案。那大概的時間複雜度是多少？ – PatrykTraveler

您可以簡單地使用2指針根據其起始位置排序塊後，如果它們的起始位置匹配，根據它們的結束位置進行排序。然後只需使用2個指針來查找最大高度。

時間複雜度：O（NlogN）

您可以找到演示鏈接here

#include <bits/stdc++.h> 
using namespace std; 

#define ii pair<int,int> 

bool modified_sort(const pair<int,int> &a, 
       const pair<int,int> &b) 
{ 
    if (a.first == b.first) { 
     return (a.second <b.second); 
    } 
    return (a.first <b.first); 
} 
int main() { 
    // your code goes here 
    vector<ii> blocks; 
    int n; // no of blocks 
    int a,b; 
    cin>>n; 
    for (int i=0;i<n;i++) { 
     cin>>a>>b; 
     blocks.push_back(ii(a,b)); 
    } 
    sort(blocks.begin(), blocks.end(), modified_sort); 
    int start=0,end=0; 
    int max_height=0; 
    while(end<n) { 
     while(start<end && blocks[start].second <= blocks[end].first) 
     { 
      start++; 
     } 
     max_height = max(max_height,(end-start+1)); 
     end++; 
    } 
    cout<<max_height<<endl; 
    return 0; 
}

來源

2017-08-30 20:49:16 sourabh1024

看起來你可以存儲在一個跳躍列表您已經處理的塊。塊應按起始位置排序。然後，在每個步驟中查找重疊的塊，您應該在此跳過列表中搜索O（log n）平均值。您會發現第一個重疊塊，然後迭代到第二個重複塊，直到遇到第一個非重疊塊。因此，平均而言，您可以得到O（n *（log（n）+ m）），其中m - 是平均重疊塊的數量。在最壞的情況下，你仍然得到O（n^2）。

來源

2017-08-30 21:43:47 algrid

放置塊並計算最高塔的高度

回答

相關問題