JAVA SEGMENT TREE || BEATS 100%
Intuition\n\n### Step-by-Step Explanation:\n\n1. Class Definition:\n   - Define a static Interval class to represent a range [start, end].\n\n2. getResults Meth
# Intuition\n\n### Step-by-Step Explanation:\n\n1. **Class Definition**:\n   - Define a static `Interval` class to represent a range `[start, end]`.\n\n2. **`getResults` Method**:\n   - Initialize a `TreeSet<Interval>` to keep track of available intervals.\n   - Initialize the `TreeSet` with an interval representing the entire number line `[0, Integer.MAX_VALUE]`.\n   - Initialize a `TreeSet<Integer>` to store the positions of obstacles.\n   - Iterate through the queries and process each query based on its type.\n\n3. **`addObstacle` Method**:\n   - **Parameters**: `obstacles` (TreeSet of existing obstacles), `intervals` (TreeSet of current intervals), `obstacle` (position of the new obstacle).\n   - Find the nearest existing obstacle positions to determine the bounds of the interval containing the new obstacle:\n     - Use `floor(obstacle)` to find the largest existing obstacle less than or equal to `obstacle`.\n     - Use `ceiling(obstacle)` to find the smallest existing obstacle greater than or equal to `obstacle`.\n   - If no such bounds exist, use `0` for the lower bound and `Integer.MAX_VALUE` for the upper bound.\n   - Remove the interval `[lowerBound, upperBound]` that contains the new obstacle.\n   - Add two new intervals: `[lowerBound, obstacle]` and `[obstacle, upperBound]`.\n   - Add the new obstacle to the `obstacles` set.\n\n4. **`canPlaceBlock` Method**:\n   - **Parameters**: `intervals` (TreeSet of current intervals), `x` (upper limit of the range), `size` (size of the block to place).\n   - Iterate through the intervals in `intervals`:\n     - Check if the current interval is large enough to accommodate a block of the given `size`.\n     - Ensure the interval\'s end does not exceed `x` by taking `Math.min(current.end, x)`.\n   - If a suitable interval is found, return `true`.\n   - If no suitable interval is found, return `false`.\n\n### Main Points:\n\n- **Interval Management**:\n  - Intervals are managed in a sorted set to allow efficient insertion and deletion.\n  - Adding an obstacle splits an interval into two smaller intervals.\n\n- **Query Handling**:\n  - For a type 1 query (`[1, x]`), an obstacle is added by updating the intervals.\n  - For a type 2 query (`[2, x, sz]`), the intervals are checked to see if there is a continuous range of length `sz` within `[0, x]` that is obstacle-free.\n\n### Usage of TreeSet:\n\n- **TreeSet** ensures that intervals and obstacles are kept in a sorted order.\n- This allows efficient searching (`floor`, `ceiling`) and iteration over the intervals.\n\nThis approach leverages the efficient interval management and binary search capabilities of `TreeSet` to handle the obstacle placement and block fitting queries effectively.\n\n\n\n# Code\n```\nclass Solution {\n    static class Interval {\n        int start, end;\n        Interval(int start, int end) {\n            this.start = start;\n            this.end = end;\n        }\n    }\n\n    public List<Boolean> getResults(int[][] queries) {\n        TreeSet<Interval> intervals = new TreeSet<>((i1, i2) -> {\n            int lengthDiff = (i2.end - i2.start) - (i1.end - i1.start);\n            return lengthDiff != 0 ? lengthDiff : i1.start - i2.start; \n        });\n        intervals.add(new Interval(0, Integer.MAX_VALUE)); // initial interval is all the x axis\n        TreeSet<Integer> obstacles = new TreeSet<>();\n        List<Boolean> result = new ArrayList<>();\n        for (int[] query : queries) {\n            if (query[0] == 1) {\n                addObstacle(obstacles, intervals, query[1]);\n            } else {\n                result.add(canPlaceBlock(intervals, query[1], query[2]) ? Boolean.TRUE : Boolean.FALSE);\n            }\n        }\n        return result;\n    }\n\n    private void addObstacle(TreeSet<Integer> obstacles, TreeSet<Interval> intervals, int obstacle) {\n        Integer lowerBound = obstacles.floor(obstacle);\n        if (lowerBound == null) {\n            lowerBound = 0;\n        }\n        Integer upperBound = obstacles.ceiling(obstacle);\n        if (upperBound == null) {\n            upperBound = Integer.MAX_VALUE;\n        }\n        // replace one interval with two\n        intervals.remove(new Interval(lowerBound, upperBound));\n        intervals.add(new Interval(lowerBound, obstacle));\n        intervals.add(new Interval(obstacle, upperBound));\n        // new obstacle\n        obstacles.add(obstacle);\n    }\n\n    private boolean canPlaceBlock(TreeSet<Interval> intervals, int x, int size) {\n        Interval current = intervals.first();\n        while (current != null && current.end - current.start >= size) { // do not consider too short intervals\n            if (Math.min(current.end, x) - current.start >= size) { // ensure current.end is not too far right\n                return true;\n            }\n            current = intervals.higher(current);\n        }\n        return false;\n    }\n}\n```
['Java']