2158. Amount of New Area Painted Each Day

O(n*m) Time Limit Exceeded

```java
class Solution {
    public int[] amountPainted(int[][] paint) {
        int[] result = new int[paint.length];
        boolean[] area = new boolean[100001];
        for (int i = 0; i < paint.length; i++) {
            int start = paint[i][0];
            int end = paint[i][1];
            int count = 0;
            for (int j = start; j < end; j++) {
                if (area[j]) {
                    count++;
                }
                area[j] = true;
            }
            result[i] = end - start - count;
        }
        return result;
    }
}
```

line sweep , use TreeSet

T: O(m*n + nlogn), n is paint length, m is maxDay

S O(n)

```java
class Solution {
    public int[] amountPainted(int[][] paint) {
        int maxDay = 0;
        // calculate the entire range
        for (int[] p : paint) { 
            maxDay = Math.max(p[0], maxDay);
            maxDay = Math.max(p[1], maxDay);
        }
        List<List<int[]>> lineData = new ArrayList<>();
        for (int i = 0; i <= maxDay; i++) {
            lineData.add(new ArrayList<>());
        }
        // record line data (start, end), record in a day line
        for (int i = 0; i < paint.length; i++) {
            int start = paint[i][0];
            int end = paint[i][1];
            lineData.get(start).add(new int[] {i, 1}); // record paint idx(paintWorkday), sign
            lineData.get(end).add(new int[]{i, -1});
        }

        int[] result = new int[paint.length];
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int i = 0; i <= maxDay; i++) { // start from 0 workday
            for (int[] data : lineData.get(i)) {
                int paintWorkday = data[0];
                int sign = data[1];
                if (sign == 1) {
                    treeSet.add(paintWorkday);
                } else {
                    treeSet.remove(paintWorkday);
                }
            }
            if (!treeSet.isEmpty()) { // be careful this!
                result[treeSet.first()]++;
            }
        }
        return result;
    }
}

/*
Input: paint = [[1,4],[5,8],[4,7]]
Output: [3,3,1]

1 2 3 4 5 6 7 8
- - - - - - - - -
0 0 0 
+.  -  
        1 1 1
        +.  - 
      2 2 2
      +.  - 
        when 5 -> in treeSet(1, 2), so we always use first one -> use 1st day as the workday
        treeSet, so small workday (paint idx), is always in the head


in each day, we get the day and see is it a start sign, if not remove it
if not remove it means still this idx's workday


T: O(m*n + nlogn), n is paint length, m is maxDay
S O(n)
  
*/
```

Jump line

T: O(n*m) , n paint length, m is max value range (ex: [0, 10000], [0, 10000])

S: O(n*m)

```java
class Solution {
    public int[] amountPainted(int[][] paint) {
        int[] result = new int[paint.length];
        Map<Integer, Integer> map = new HashMap<>();

        int idx = 0;
        for (int[] p : paint) {
            int work = 0;
            int start = p[0];
            int end = p[1];
            while (start < end) {
                if (map.containsKey(start)) {
                    int preEnd = map.get(start);
                    map.put(start, Math.max(preEnd, end));
                    start = preEnd;
                } else {
                    map.put(start, end);
                    start++;
                    work++;
                }
            }
            result[idx++] = work;
        }
        return result;
    }
}

/*
T: O(n*m) , n paint length, m is max value range (ex: [0, 10000], [0, 10000])
S: O(n*m)

[[1,4],[4,7],[5,8]]


paint[0], s = 1 e = 4
map(1,4)
s = 2
w = 1

map(2,4)
s = 3
w = 2

map(3,4)
s = 4
w = 3
end while
result[0] = 3
---
paint[1], s = 4 e = 7
map(4,7)
s = 5
w = 1

map(5,7)
s = 6
w = 2

map(6,7)
s = 7
w = 3
end while
result[1] = 3

---------
paint[2], s = 5 e = 8
map(5) -> exists
                    int preEnd = map.get(5); => 7
                    map.put(start, Math.max(preEnd, end)); map(5, max(7, 8))
                    start = preEnd; start = 7 (jump!!)

map(7,8)
s = 8
w = 1
end while
result[2] = 1

so result[3,3,1]
*/
```ja