放置积木和计算最高塔的高度

Question

给出了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.

Answer 1

在根据块的开始位置对块进行排序后，如果块的开始位置与块的开始位置匹配，则可以简单地使用2 pointers。然后简单地使用这两个指针来找到最大高度。

时间复杂度：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;
}

Answer 2

这是一个简单的解决方案(没有跳过列表)：

创建数组heights

遍历这些块。

对于每个数据块

• 通过迭代来检查高度数组中的现有条目，了解当前块所占据的位置。确定它们的高度将当前区块的高度数组中的值与上一步中确定的高度相乘。
• 保存扫描过程中构建的最大塔的分数。

Answer 3

这个问题与图的遍历同构。每个间隔(块)是图的一个节点。当它们的间隔重叠时，两个块通过边连接(堆叠的可能性)。你给出的例子有图的边

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

最高堆栈与图中最长的无圈路径同构。这个问题有众所周知的解决方案。

顺便说一句，我不认为你的n^2算法适用于所有的块排序。尝试一组六个块，每个块有一个重叠，例如间隔n，n+3 for n in {2，4，6，8，10，12}。将这些块的所有排列提供给您的算法，并查看每个块的高度是否为6。

复杂性

我认为最高的复杂性可能是对间隔进行排序，以加速标记边缘。排序将是log ( n)。添加边是O(n d)，其中d是图的平均度( n*d是边的数量)。

我在脑海中没有确切的graph traversal algorithm，但我希望它是O(d log )。