Java Solution | Easy to Understand | Beats 100%
Intuition\nThe problem is about placing blocks on a line and checking if a block of a certain size can be placed at a certain position. The line starts with a b
# Intuition\nThe problem is about placing blocks on a line and checking if a block of a certain size can be placed at a certain position. The line starts with a block at position 0. The queries are of two types: adding a block at a certain position and checking if a block of a certain size can be placed at a certain position.\n\n# Approach\nThe approach uses a TreeSet blocks to store the positions of the blocks and a HashMap maxDis to store the maximum distance from each block to its previous block.\n\nFor each query, if it\'s an add block query, it adds the block to the TreeSet and updates the maximum distance for the current block and the next block.\n\nIf it\'s a check query, it checks if the block can be placed at the position by checking if the size is less than or equal to the maximum distance from the block at the position to its previous block.\n\n# Complexity\n- Time complexity:\nThe time complexity is $$O(n log n)$$, where n is the number of queries. This is because for each query, it performs operations on a TreeSet and a HashMap, which take $$O(log n)$$ time.\n\n- Space complexity:\nThe space complexity is $$O(n)$$, where n is the number of queries. This is because it stores the positions of the blocks in a TreeSet and the maximum distances in a HashMap, which can have at most $$n$$ entries.\n\n# Code\n```java\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```
['Array', 'Hash Table', 'Greedy', 'Simulation', 'Java']