Drop squares and get maximum height


  • 1
    L

    There is a board without left and right boundaries. void drop(float x, float size) drops squares with size of (sizesize) starting from x. It will finally locate on the top of existing squares.
    For example, drop(0, 2) will get:(a represent a square with size 1
    1)

    • aa
    • aa
    • ------------------bottom line
    • 01 the position
      (The maximum height of the board is 2)

    Then drop(1,3):

    • _aaa
    • _aaa
    • _aaa
    • aa
    • aa
    • ------------------bottom line
    • 0123 the position
      (The maximum height of the board is 5)

    Then drop(5,1):

    • _aaa
      
    • _aaa
      
    • _aaa
      
    • aa
    • aa____a
    • ------------------bottom line
    • 012345 the position
      (The maximum height of the board is 5)

    Maintain the board after each call to drop(). We may run the function - int getMaxHeight() at any time. We should get the maximum height of the board using O(1) time.

    Notice that in the types of arguments in drop() function are both float. So the position is not necessarily an integer.


  • 0
    W

    @litianhao Method 1: using BST
    § If the input is float
    § Insert the square to a set (BST), squares are sorted in ascending order of the start. No square is overlapped.
    § When a new square comes, find the lower bound, but need to precede by one if the previous square ends after its start.
    § Delete those overlapping squares, but need to insert the remaining part of the partially-overlapping square.
    § Get the maximum height while deleting, renew the height of the input square and insert it.

    #include <iostream>
    #include <set>
    #include <cmath>
    #include <assert.h>
    
    using namespace std;
    
    struct Interval {
        double start, end, height;
        Interval(double start, double end, double height): start(start), end(end), height(height) {}
    };
    
    struct squareCmp {
        bool operator()(Interval inter1, Interval inter2) {
            return inter1.start < inter2.start;
        }
    };
    
    class DropSquare {
    public:
        DropSquare() {}
        
        void drop(double start, double size) {
            Interval interval(start, start + size, size);
            auto iter = intervals.lower_bound(interval);
            double maxHei = 0.0;
            // delete partially overlapping interval, insert the non-overlapping segment back.
            if(iter != intervals.begin() && prev(iter)->end > interval.start) {
                iter--;
                maxHei = max(maxHei, iter->height);
                Interval remain(iter->start, interval.start, iter->height);
                iter = intervals.erase(iter);
                intervals.insert(iter, remain);
            }
            // delete fully overlapping intervals, renew the maximum height.
            while(iter != intervals.end() && iter->end <= interval.end) {
                maxHei = max(maxHei, iter->height);
                iter = intervals.erase(iter);
            }
            // delete the partially overlapping interval, insert the non-overlapping segment back.
            if(iter != intervals.end() && iter->start < interval.end) {
                maxHei = max(maxHei, iter->height);
                Interval remain(interval.end, iter->end, iter->height);
                iter = intervals.erase(iter);
                iter = intervals.insert(iter, remain);
            }
            interval.height += maxHei;
            intervals.insert(iter, interval);
        }
        
        double getHeight(double start, double end) {
            Interval interval(start, end, 0);
            auto iter = intervals.lower_bound(interval);
            if(iter != intervals.begin() && prev(iter)->end > interval.start) iter--;
            double maxHei = 0.0;
            for(; iter != intervals.end() && iter->start < interval.end; iter++) {
                maxHei = max(maxHei, iter->height);
            }
            return maxHei;
        }
        
    private:
        set<Interval, squareCmp> intervals;
    };
    
    int main(int argc, const char * argv[]) {
        DropSquare sol;
        sol.drop(0.8, 2.0);
        sol.drop(2.5, 1.5);
        sol.drop(4.2, 2.0);
        sol.drop(1.5, 3);
        assert(abs(sol.getHeight(0.8, 7) - 6.5) <= 0.0001);
        return 0;
    }
    

    Method 2: A standard segment tree solution, given the range and precision. The following solution assume the input is integer, but once we know the precision of the double input, we can use the minimum unit as a bucket to simulate double precision.

    #include <iostream>
    #include <vector>
    #include <assert.h>
    
    using namespace std;
    
    struct Node {
        Node* left, *right;
        int start, end, maxHei;
        Node(int s, int e): start(s), end(e), maxHei(0), left(NULL), right(NULL) {}
    };
    
    class SegTree {
    public:
        SegTree(int mr): minRange(1), maxRange(mr) {
            root = build(minRange, maxRange); // Initialize a range with height 0.
        }
        
        void drop(int position, int size) {
            int start = position, end = position + size - 1;
            int newHei = query(root, start, end) + size;
            modify(root, start, end, newHei);
        }
        
        int getHeight(int start, int end) {
            return query(root, start, end);
        }
        
    private:
        Node* root;
        int minRange, maxRange;
        
        Node* build(int start, int end) {
            if(start > end) return NULL;
            if(start == end) {
                Node* newnode = new Node(start, start);
                return newnode;
            }
            Node* node = new Node(start, end);
            int mid = start + (end - start) / 2;
            node->left = build(start, mid);
            node->right = build(mid+1, end);
            return node;
        }
        
        int query(Node* node, int start, int end) {
            if(!node) return INT_MIN;
            if(node->start >= start && node->end <= end) return node->maxHei;
            if(node->start > end || node->end < start) return INT_MIN;
            return max(query(node->left, start, end), query(node->right, start, end));
        }
        
        void modify(Node* node, int start, int end, int newHei) {
            if(node->start > end || node->end < start) return;
            if(node->start == node->end) {
                node->maxHei = newHei;
                return;
            }
            modify(node->left, start, end, newHei);
            modify(node->right, start, end, newHei);
            node->maxHei = max(node->left->maxHei, node->right->maxHei);
        }
        
    };
    
    int main(int argc, const char * argv[]) {
        int maxRange = 10;
        SegTree seg(maxRange);
        seg.drop(1, 2);
        seg.drop(5, 3);
        assert(seg.getHeight() == 3);
        seg.drop(2, 4);
        assert(seg.getHeight() == 7);
        seg.drop(8, 3);
        assert(seg.getHeight() == 7);
        seg.drop(1, 4);
        assert(seg.getHeight() == 11);
        seg.drop(7, 2);
        return 0;
    }
    

  • 0
    E

    Storing the lowest clear Y position per column.

    
    class Solution {
      
      private static int TAKEN = 8;
      private static int NOT_TAKEN = 1;
      
      
      public static void drop(int x, int size, int[][] map) {
        int lowestClearY = getLowestClearY(x, size, map[map.length-1]);
        applyShape(x,lowestClearY,size,map);
      }
      
      public static int getLowestClearY(int x, int size, int[] map){
        int lowestClearY = 0;
        for (int xIter = x; xIter < x + size; xIter++) {
          System.out.println(map[xIter]);
          if (map[xIter] > lowestClearY) {
            lowestClearY = map[xIter];
          }
        }
          
        return lowestClearY; 
      }
      
      public static void applyShape(int x, int y, int size, int[][] map) {
        
        for (int yIter = y; yIter < y + size; yIter++) {
          for ( int xIter = x; xIter < x + size; xIter++) {
            System.out.println("@" + xIter + "," + yIter);
            map[yIter][xIter] = TAKEN; 
            
            // store the new lowestClearY in top of map
            map[map.length-1][xIter] = yIter + 1;
          }
        }
        
      }
      
      
      public static void main(String[] args) {
        //                     y,x
        int[][] map = new int[21][10];
        
        // top row is reserved for storing lowest clear row per column
        Arrays.fill(map[map.length-1], 0, map[map.length-1].length, 0);
        
        for (int y = 0; y < map.length-1; y++){
          Arrays.fill(map[y], 0, map[y].length, NOT_TAKEN);
        }
          // Test getLowestClearY
    //     System.out.println("expecting 3: " + 
    //                        getLowestClearY(2,3,new int[] {
    //                           6,6,2,3,1,6,6
    //                        }));
        
        // visually test dropping squares
        drop(0,2, map);
        drop(1,2, map);
        drop(0,2, map);
        drop(2,2, map);
        
        // visually test applyShape
        // applyShape(2,2,2,map);
        
        System.out.println("Lowest clear y:");
        System.out.println(Arrays.toString(map[map.length-1]));
        System.out.println("");
        
        for (int y = map.length-2; y >= 0; y--){
          System.out.println(Arrays.toString(map[y]));
        }
      }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.