Persistent Ordered Set | No Query Sort | O(n lg n + k lg n) time | O(n lg n) space
Intuition\nWe want to find the closest room. An ordered set solves this problem in O(\textrm{lg } n) time. However, there is an additional constraint: the room 
# Intuition\nWe want to find the closest room. An ordered set solves this problem in $$O(\\textrm{lg } n)$$ time. However, there is an additional constraint: the room must have size greater than or equal to some threshold. If we had access to the ordered set that contained only the rooms with size greater than or equal to the threshold, this would be simple. Assuming the rooms are inserted with decreasing size, for each threshold we will have the correct ordered set at some timestep $$t$$. In fact, we can simply sort the queries and process them as we build the ordered set. \n\nWhile this is enough to solve the problem, this approach might not work in the real world. Queries are often not all known ahead of time. How can we solve this problem without sorting the queries? \n\n# Approach\n\nWe can save the state of the ordered set at each timestep $$t$$ during construction. Naively, this will take $$O(n^2)$$ space which leads to TLE. However, instead of cloning the entire set, we can only clone the parts that change. With a balanced tree, like an AVL tree, this is only $$O(\\textrm{lg } n)$$ nodes. Hence, each insertion will take $$O(\\textrm{lg } n)$$ memory and $$O(\\textrm{lg } n)$$ time. We can find the correct version of the ordered set for a given query with binary search in $$O(\\textrm{lg } n)$$ time. Hence, we can solve the problem in $$O(n \\textrm{ lg } n + k \\textrm{ lg } n)$$ time and $$O(n \\textrm{ lg } n)$$ space.\n\n# Analysis\n\nIt\'s interesting that all prior versions of the ordered set can be maintained while only incurring a log factor in the space complexity. The basic idea is that each insertion operation on a balanced binary tree can only change $$O(\\textrm{lg } n)$$ nodes and so each insertion only costs $$O(\\textrm{lg } n)$$ space.\n\nThe $$i$$-th insertion into the AVL tree will modify $$c_i \\textrm{ lg } i$$ nodes for some $$c_i > 0$$ since the AVL tree is balanced. The total number of modified nodes over all insertions is $$\\sum\\limits_{i=1}^n c_i \\textrm{ lg } i$$. Let $$c_{\\textrm{min}}$$ and $$c_{\\textrm{max}}$$ denote the smallest and largest $$c_i$$ respectively. \n\nNote that $$\\int\\limits_{1}^{n} c_{min} \\textrm{ lg } x \\leq \\sum\\limits_{i=1}^n c_i \\textrm{ lg } i \\leq \\int\\limits_{1}^{n} c_{max} \\textrm{ lg } (x + 1)$$. Also $$\\int\\limits_{1}^{n} c_{min} \\textrm{ lg } x = c_{min} (n \\textrm{ lg } n - n + C) = \\Theta(n \\textrm{ lg } n)$$ and $$\\int\\limits_{1}^{n} c_{max} \\textrm{ lg } x = c_{max} (n \\textrm{ lg } n - n + C) = \\Theta(n \\textrm{ lg } n)$$. Hence $$\\sum\\limits_{i=1}^n c_i \\textrm{ lg } i = \\Theta(n \\textrm{ lg } n)$$. \n\n# Code\n\nHere is a quick and dirty implementation. The underlying data structure for the persistent ordered set is a persistent AVL tree. The code is not great but hopefully it illustrates the main idea.\n\n```\nclass PersistentOrderedSet {\n\nprivate:\n\tstruct Node {\n\t\tint key;\n\t\tint height;\n\t\tNode* left;\n\t\tNode* right;\n\n\t\tNode(int key) : key(key), height(0), left(nullptr), right(nullptr) { }\n\t\tNode(int key, int height, Node* left, Node* right)\n\t\t\t: key(key), height(height), left(left), right(right) { }\n\t};\n\n\tvector<Node*> m_roots;\n\n\tint height(Node* root) {\n\t\treturn root != nullptr ? root->height : 0;\n\t}\n\n\tbool balanced(Node* left, Node* right) {\n\t\treturn abs(height(left) - height(right)) < 2;\n\t}\n\n\tNode* balance(Node* root, Node* left, Node* right, int key) {\n\t\tNode *a, *b, *c, *d, *x, *y, *z;\n\n\t\tif (height(left) - height(right) == 2) {\n\t\t\tif (key > left->key) {\n\t\t\t\tz = root;\n\t\t\t\tx = left;\n\t\t\t\td = right;\n\t\t\t\ta = x->left;\n\t\t\t\ty = x->right;\n\t\t\t\tb = y->left;\n\t\t\t\tc = y->right;\n\t\t\t} else {\n\t\t\t\tz = root;\n\t\t\t\ty = left;\n\t\t\t\td = right;\n\t\t\t\tx = y->left;\n\t\t\t\tc = y->right;\n\t\t\t\ta = x->left;\n\t\t\t\tb = x->right;\n\t\t\t}\n\t\t} else {\n\t\t\tif (key < right->key) {\n                x = root;\n                a = left;\n                z = right;\n                y = z->left;\n                d = z->right;\n                b = y->left;\n                c = y->right;\n\t\t\t} else {\n\t\t\t\tx = root;\n                a = left;\n                y = right;\n                b = y->left;\n                z = y->right;\n                c = z->left;\n                d = z->right;\n\t\t\t}\n\t\t}\n\n\t\tauto xh = 1 + max(height(a), height(b));\n\t\tauto zh = 1 + max(height(c), height(d));\n\t\tauto yh = 1 + max(xh, zh);\n\n\t\treturn new Node(\n\t\t\ty->key, \n\t\t\tyh, \n\t\t\tnew Node(x->key, xh, a, b),\n\t\t\tnew Node(z->key, zh, c, d)\n\t\t);\n\t}\n\n\tNode* insert(Node* root, int key) {\n\t\tif (root == nullptr) {\n\t\t\treturn new Node(key);\n\t\t}\n\n\t\tif (key == root->key) {\n\t\t\treturn root;\n\t\t}\n\n\t\tauto left = root->left;\n\t\tauto right = root->right;\n\n\t\tif (key < root->key) {\n\t\t\tleft = insert(root->left, key);\n\t\t} else {\n\t\t\tright = insert(root->right, key);\n\t\t}\n\n\t\tif (balanced(left, right)) {\n\t\t\tauto h = 1 + max(height(left), height(right));\n\t\t\treturn new Node(root->key, h, left, right); \n\t\t}\n\n\t\treturn balance(root, left, right, key);\n\t}\n\n\tNode* predecessor(Node* root, int key) {\n        if (root == nullptr) {\n            return nullptr;\n        }\n\n        if (key == root->key && root->left != nullptr) {\n            auto pred = root->left;\n            while (pred->right != nullptr) {\n                pred = pred->right;\n            }\n            return pred;\n        }\n\n        if (key <= root->key) {\n            return predecessor(root->left, key);\n        }\n\n        auto pred = predecessor(root->right, key);\n        return pred == nullptr || root->key > pred->key ? root : pred;\n    }\n\n\n    Node* successor(Node* root, int key) {\n        if (root == nullptr) {\n            return nullptr;\n        }\n\n        if (key == root->key && root->right != nullptr) {\n            auto succ = root->right;\n            while (succ->left != nullptr) {\n                succ = succ->left;\n            }\n            return succ;\n        }\n\n        if (key >= root->key) {\n            return successor(root->right, key);\n        }\n\n        auto succ = successor(root->left, key);\n        return succ == nullptr || root->key < succ->key ? root : succ;\n    }\n\npublic:\n\tPersistentOrderedSet() : m_roots{nullptr} { }\n\n\tvoid insert(int key) {\n\t\tauto root = insert(m_roots.back(), key);\n\t\tm_roots.push_back(root);\n\t}\n\n\toptional<int> predecessor(int t, int key) {\n\t\tauto pred = predecessor(m_roots[t], key);\n\t\tif (pred == nullptr)\n\t\t\treturn nullopt;\n\t\treturn make_optional(pred->key);\n\t}\n\n\toptional<int> successor(int t, int key) {\n\t\tauto succ = successor(m_roots[t], key);\n\t\tif (succ == nullptr)\n\t\t\treturn nullopt;\n\t\treturn make_optional(succ->key);\n\t}\n};\n\nclass Solution {\npublic:\n    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {\n        auto cmp = [](const vector<int>& a, const vector<int>& b) {\n            return a[1] < b[1];\n        };\n\n        sort(rooms.begin(), rooms.end(), cmp);\n\n        PersistentOrderedSet s;\n        for (int i = rooms.size() - 1; i >= 0; --i) {\n            s.insert(rooms[i][0]);\n        }\n\n        vector<int> ans;\n        for (int i = 0; i < queries.size(); ++i) {\n            auto t = rooms.end() - lower_bound(rooms.begin(), rooms.end(), queries[i], cmp);\n            auto pred = s.predecessor(t, queries[i][0] + 1);\n            auto succ = s.successor(t, queries[i][0] - 1);\n\n            if (pred == nullopt && succ == nullopt) {\n                ans.push_back(-1);\n            } else if (pred == nullopt) {\n                ans.push_back(succ.value());\n            } else if (succ == nullopt) {\n                ans.push_back(pred.value());\n            } else if (queries[i][0] - pred.value() <= succ.value() - queries[i][0]) {\n                ans.push_back(pred.value());\n            } else {\n                ans.push_back(succ.value());\n            }\n        }\n\n        return ans;\n    }\n};\n```
['Binary Search', 'Ordered Set', 'C++']