699.Falling Squares

1- O(n^2)

https://discuss.leetcode.com/topic/107107/easy-understood-o-n-2-solution-with-explanation/2

class Solution {
    public List<Integer> fallingSquares(int[][] positions) {
        List<Interval> intervals = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        int curHeight = 0;
        for(int[] pos : positions){
            Interval cur = new Interval(pos[0], pos[0] + pos[1], pos[1]);
            curHeight = Math.max(curHeight, getHeight(intervals, cur));
            ans.add(curHeight);
            intervals.add(cur);

        }
        return ans;
    }

    public int getHeight(List<Interval> intervals, Interval cur){
        int preMaxHeight = 0;
        for(Interval i : intervals){
            if(i.left >= cur.right || i.right <= cur.left)
                continue;
            preMaxHeight =  Math.max(preMaxHeight, i.height);
        }
        cur.height += preMaxHeight;
        return cur.height;
    }
}

class Interval{
    int left;
    int right; 
    int height;
    public Interval(int left, int right, int height){
        this.left = left;
        this.right = right;
        this.height = height;
    }
}