@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; }