CODEWITHSUNDEEP
algorithm
PatrykTraveler
PatrykTraveler

Reputation: 105

Placing blocks and calculating height of the highest tower

Series of k blocks is given (k1, k2, ..., ki). Each block starts on position ai and ends on position bi and its height is 1. Blocks are placed consecutively. If the block overlaps another one, it is being attached on its top. My task is to calculate the highest tower of blocks. I have created an algorithm which time complexity is about O(n^2), but I know there is a faster solution with the usage of 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.

Upvotes: 1

Views: 1258

Answers (4)

algrid
algrid

Reputation: 5954

It looks like you can store your already processed blocks in a skip list. The blocks should be ordered by starting position. Then to find overlapping blocks at each step you should search in this skip list which is O(log n) on average. You find first overlapping block then iterate to next and so on until you meet first non-overlapping block.

So on average you can get O(n * (log(n) + m)) where m - is the mean number of overlapping blocks. In the worst case you still get O(n^2).

Upvotes: 0

Prune
Prune

Reputation: 77875

This problem is isomorphic to a graph traversal. Each interval (block) is a node of the graph. Two blocks are connected by an edge iff their intervals overlap (a stacking possibility). The example you give has graph edges

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

Your highest stack is isomorphic to the longest cycle-free path in the graph. This problem has well-known solutions.

BTW, I don't think your n^2 algorithm works for all orderings of blocks. Try a set of six blocks with one overlap each, such as the intervals [n, n+3] for n in {2, 4, 6, 8, 10, 12}. Feed all permutations of these blocks to your algorithm, and see whether it comes up with a height of 6 for each.

Complexity

I think the highest complexity is likely to be sorting the intervals to accelerate marking the edges. The sort will be O(n log n). Adding edges is O(n d) where d is the mean degree of the graph (and n*d is the number of edges).

I don't have the graph traversal algorithm solidly in mind, but I expect that it's O(d log n).

Upvotes: 0

sourabh1024
sourabh1024

Reputation: 657

You can simply use 2 pointers after sorting the blocks based on their starting positions, if their starting positions match sort them based on their ending positions. Then simply use the 2 pointers to find the maximum height.

Time complexity : O(NlogN)

You can find the demo link 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;
}

Upvotes: 1

neuhaus
neuhaus

Reputation: 4094

Here is a straightforward solution (without skip lists):

Create an array heights

Iterate through the blocks.

For every block

  • Check the existing entries in the heights array for the positions the current block occupies by iterating over them. Determine their maximum.

  • Increase the values in the heights array for the current block to the maximum+1 determined in the previous step.

  • keep score of the maximum tower you have built during the scan.

Upvotes: 0

Related Questions