TreeSets with explanation
Approach\nLet\'s maintain TreeSet with longest free intervals (cuts) on top.\nUpon adding obstacle we\'ll remove a cut with this obstacle from the TreeSet and a
# Approach\nLet\'s maintain TreeSet with longest free intervals (cuts) on top.\nUpon adding obstacle we\'ll remove a cut with this obstacle from the TreeSet and add two new cuts. To do so we\'ll need second TreeSet with obstacle coordinates.\nWhen searching for a place for a block we\'ll start from the longest cut and proceed with checks until current cut is longer than given sz. The check is ```Math.min(cur.end, x) - cur.start >= sz``` to ensure the cut is not too far right.\n\n# Complexity\n```n = queries.length```\nWorst case runtime complexity is $$O(n ^ 2 logn)$$ since ```cur = cuts.higher(cur);``` is $$O(logn)$$ and the worst case scenario is to have n / 2 obstacles first and then n / 2 searches with sz = 1 resulting in $$O(n logn)$$ for each query.\nThe more obstacles are added, the less average cut size will be thus when searching for high sz we\'ll have to iterate through less cuts. So the best-case scenario for single search is under $$O(n logn)$$.\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    static class Pair {\n        int start, end;\n        Pair(int s, int e) {\n            start = s;\n            end = e;\n        }\n    }\n\n    public List<Boolean> getResults(int[][] queries) {\n        TreeSet<Pair> cuts = new TreeSet<>((p1, p2) -> {\n            int diffLen = (p2.end - p2.start) - (p1.end - p1.start);\n            return diffLen != 0 ? diffLen : p1.start - p2.start; \n        });\n        cuts.add(new Pair(0, Integer.MAX_VALUE)); // initial cut is all the x axis\n        TreeSet<Integer> obstacles = new TreeSet<>();\n        List<Boolean> result = new ArrayList<>();\n        for (int i = 0; i < queries.length; i++) {\n            if (queries[i][0] == 1) {\n                int x = queries[i][1];\n                Integer floor = obstacles.floor(x);\n                if (floor == null) {\n                    floor = 0;\n                }\n                Integer ceil = obstacles.ceiling(x);\n                if (ceil == null) {\n                    ceil = Integer.MAX_VALUE;\n                }\n                // replace one cut with two\n                cuts.remove(new Pair(floor,  ceil));\n                cuts.add(new Pair(floor, x));\n                cuts.add(new Pair(x, ceil));\n                // new obstacle\n                obstacles.add(x);\n            } else {\n                int x = queries[i][1];\n                int sz = queries[i][2];\n                Pair cur = cuts.first();\n                boolean success = false;\n                while (cur != null && cur.end - cur.start >= sz) { // do not consider too short cuts\n                    if (Math.min(cur.end, x) - cur.start >= sz) { // ensure cur.end is not too far right\n                        success = true;\n                        result.add(true);\n                        break;\n                    }\n                    cur = cuts.higher(cur);\n                }\n                if (!success) {\n                    result.add(false);\n                }\n            }\n        }\n        return result;\n    }\n}\n```
['Java']