🚧 Efficient Obstacle Management on an Infinite Number Line 🚀
Intuition and Approach\n\nThe problem requires handling two types of queries on an infinite number line:\n1. Placing obstacles at specified positions.\n2. Check
## Intuition and Approach\n\nThe problem requires handling two types of queries on an infinite number line:\n1. Placing obstacles at specified positions.\n2. Checking if a block of a specified size can fit within a given range without intersecting any obstacles.\n\n### Key Ideas\n1. **Data Structures**:\n   - Use an `OrderedSet` (or `set` in C++) to store obstacle positions.\n   - Use an `OrderedMap` (or `map<int, set<int>>` in C++) to keep track of available spaces between obstacles, grouped by size.\n\n2. **Handling Type 1 Queries**:\n   - When an obstacle is placed, split the existing space it intersects into two new spaces. Update the `OrderedMap` accordingly.\n\n3. **Handling Type 2 Queries**:\n   - Check if any available space in the `OrderedMap` can accommodate the block without exceeding the specified boundary. Iterate over possible start positions efficiently.\n\n### Detailed Steps\n\n1. **Initialization**:\n   - Insert two dummy obstacles at positions 0 and the maximum possible distance (`maxi_dist`) to simplify edge case handling.\n   - Initialize the available space to cover the range from 0 to `maxi_dist`.\n\n2. **Breaking Spaces**:\n   - For a Type 1 query, find the neighboring obstacles (`pos_prev` and `pos_next`).\n   - Remove the original space and add two new spaces resulting from the split.\n\n3. **Finding Spaces**:\n   - For a Type 2 query, iterate over possible block sizes starting from the requested size.\n   - Check if the block can fit within the specified range using the first start position of each space size group (since start positions are ordered).\n\n### Complexity\n- **Time Complexity**:\n  - **Type 1 Queries**: Insertion and splitting spaces take \\(O(\\log n)\\).\n  - **Type 2 Queries**: Checking available spaces can take up to \\(O(\\sqrt{m})\\) in the worst case, where \\(m\\) is the maximum distance.\n\n- **Space Complexity**:\n  - Storing obstacles and spaces takes \\(O(n)\\).\n\n### Code Implementation\n\n#### C++\n```cpp\n#include <vector>\n#include <set>\n#include <map>\nusing namespace std;\n\nclass Solution {\n    void breakSpaces(int pos) {\n        auto it = obstacles.upper_bound(pos);\n        int pos_next = *it;\n        int pos_prev = *prev(it);\n        \n        int orig_size = pos_next - pos_prev;\n        spaces[orig_size].erase(pos_prev);\n        if (spaces[orig_size].empty()) spaces.erase(orig_size);\n\n        spaces[pos - pos_prev].insert(pos_prev);\n        spaces[pos_next - pos].insert(pos);\n    }\n\n    bool findSpace(int maxi_dist, int block_size) {\n        auto it = spaces.lower_bound(block_size);\n        while (it != spaces.end()) {\n            int first_pos = *it->second.begin();\n            if (first_pos + block_size <= maxi_dist) {\n                return true;\n            }\n            ++it;\n        }\n        return false;\n    }\n\n    vector<bool> ans;\n    set<int> obstacles;\n    map<int, set<int>> spaces;\n\npublic:\n    vector<bool> getResults(const vector<vector<int>>& queries) {\n        int nquery = queries.size();\n        ans.reserve(nquery);\n        int maxi_dist = min(50000, 3 * nquery);\n        obstacles.insert(0);\n        obstacles.insert(maxi_dist);\n        spaces[maxi_dist].insert(0);\n\n        for (const auto& query : queries) {\n            int op = query[0];\n            if (op == 1) {\n                breakSpaces(query[1]);\n                obstacles.insert(query[1]);\n            } else {\n                ans.push_back(findSpace(query[1], query[2]));\n            }\n        }\n        return ans;\n    }\n};\n```\n\n#### Python\n```python\nclass Solution:\n    def __init__(self):\n        self.ans = []\n        self.obstacles = set()\n        self.spaces = {}\n\n    def break_spaces(self, pos):\n        it = sorted(self.obstacles)\n        pos_next = next(x for x in it if x > pos)\n        pos_prev = next(x for x in reversed(it) if x < pos)\n\n        orig_size = pos_next - pos_prev\n        self.spaces[orig_size].remove(pos_prev)\n        if not self.spaces[orig_size]:\n            del self.spaces[orig_size]\n\n        self.spaces.setdefault(pos - pos_prev, set()).add(pos_prev)\n        self.spaces.setdefault(pos_next - pos, set()).add(pos)\n\n    def find_space(self, maxi_dist, block_size):\n        for size in sorted(self.spaces):\n            if size >= block_size:\n                first_pos = min(self.spaces[size])\n                if first_pos + block_size <= maxi_dist:\n                    return True\n        return False\n\n    def getResults(self, queries):\n        nquery = len(queries)\n        maxi_dist = min(50000, 3 * nquery)\n        self.obstacles.update([0, maxi_dist])\n        self.spaces[maxi_dist] = {0}\n\n        for query in queries:\n            op = query[0]\n            if op == 1:\n                self.break_spaces(query[1])\n                self.obstacles.add(query[1])\n            else:\n                self.ans.append(self.find_space(query[1], query[2]))\n\n        return self.ans\n```\n\n#### Java\n```java\nimport java.util.*;\n\nclass Solution {\n    private List<Boolean> ans;\n    private TreeSet<Integer> obstacles;\n    private TreeMap<Integer, TreeSet<Integer>> spaces;\n\n    public Solution() {\n        ans = new ArrayList<>();\n        obstacles = new TreeSet<>();\n        spaces = new TreeMap<>();\n    }\n\n    private void breakSpaces(int pos) {\n        Integer pos_next = obstacles.higher(pos);\n        Integer pos_prev = obstacles.lower(pos);\n\n        int orig_size = pos_next - pos_prev;\n        spaces.get(orig_size).remove(pos_prev);\n        if (spaces.get(orig_size).isEmpty()) spaces.remove(orig_size);\n\n        spaces.computeIfAbsent(pos - pos_prev, k -> new TreeSet<>()).add(pos_prev);\n        spaces.computeIfAbsent(pos_next - pos, k -> new TreeSet<>()).add(pos);\n    }\n\n    private boolean findSpace(int maxi_dist, int block_size) {\n        for (Map.Entry<Integer, TreeSet<Integer>> entry : spaces.tailMap(block_size).entrySet()) {\n            int first_pos = entry.getValue().first();\n            if (first_pos + block_size <= maxi_dist) {\n                return true;\n            }\n        }\n        return false;\n    }\n\n    public List<Boolean> getResults(List<int[]> queries) {\n        int nquery = queries.size();\n        int maxi_dist = Math.min(50000, 3 * nquery);\n        obstacles.add(0);\n        obstacles.add(maxi_dist);\n        spaces.computeIfAbsent(maxi_dist, k -> new TreeSet<>()).add(0);\n\n        for (int[] query : queries) {\n            int op = query[0];\n            if (op == 1) {\n                breakSpaces(query[1]);\n                obstacles.add(query[1]);\n            } else {\n                ans.add(findSpace(query[1], query[2]));\n            }\n        }\n        return ans;\n    }\n}\n```\n\n#### JavaScript\n```javascript\nclass Solution {\n    constructor() {\n        this.ans = [];\n        this.obstacles = new Set();\n        this.spaces = new Map();\n    }\n\n    breakSpaces(pos) {\n        const it = Array.from(this.obstacles).sort((a, b) => a - b);\n        const pos_next = it.find(x => x > pos);\n        const pos_prev = [...it].reverse().find(x => x < pos);\n\n        const orig_size = pos_next - pos_prev;\n        this.spaces.get(orig_size).delete(pos_prev);\n        if (this.spaces.get(orig_size).size === 0) this.spaces.delete(orig_size);\n\n        if (!this.spaces.has(pos - pos_prev)) this.spaces.set(pos - pos_prev, new Set());\n        this.spaces.get(pos - pos_prev).add(pos_prev);\n\n        if (!this.spaces.has(pos_next - pos)) this.spaces.set(pos_next - pos, new Set());\n        this.spaces.get(pos_next - pos).add(pos);\n    }\n\n    findSpace(maxi_dist, block_size) {\n        for (const [size, positions] of [...this.spaces.entries()].sort(([a], [b]) => a - b)) {\n            if (size >= block_size) {\n                const first_pos = Math.min(...positions);\n                if (first_pos + block_size <= maxi_dist) {\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n\n    getResults(queries) {\n        const nquery = queries.length;\n        const maxi_dist = Math.min(50000, 3 * nquery);\n        this.obstacles.add(0);\n        this.obstacles.add(maxi_dist);\n        if (!this.spaces.has(maxi_dist)) this.spaces.set(maxi_dist, new Set());\n        this.spaces.get(maxi_dist).add(0);\n\n        for (const query of queries) {\n            const op = query[0];\n            if (op === 1) {\n                this.breakSpaces(query[1]);\n                this.obstacles.add(query[1]);\n            } else {\n                this.ans.push(this.findSpace(query[1], query[2]));\n            }\n        }\n        return this.ans;\n    }\n}\n```
['Python', 'C++', 'Java', 'Python3', 'JavaScript']