Skip to content

2158. Amount of New Area Painted Each Day 👍

Approach 1: Sweep Line

  • Time: $O(\max(\texttt{paint[i][0]}) + \texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
enum class Type { kEntering, kLeaving };

struct Event {
  int day;
  int index;
  Type type;
  Event(int day, int index, Type type) : day(day), index(index), type(type) {}
};

class Solution {
 public:
  vector<int> amountPainted(vector<vector<int>>& paint) {
    const int n = paint.size();
    const int minDay = (*ranges::min_element(
        paint, ranges::less{}, [](const vector<int>& p) { return p[0]; }))[0];
    const int maxDay = (*ranges::max_element(
        paint, ranges::less{}, [](const vector<int>& p) { return p[1]; }))[1];
    vector<int> ans(n);
    vector<Event> events;
    // Stores the indices of paints that are available now.
    set<int> runningIndices;

    for (int i = 0; i < n; ++i) {
      const int start = paint[i][0];
      const int end = paint[i][1];
      events.emplace_back(start, i, Type::kEntering);  // 1 := entering
      events.emplace_back(end, i, Type::kLeaving);     // -1 := leaving
    }

    ranges::sort(events,
                 [](const auto& a, const auto& b) { return a.day < b.day; });

    int i = 0;  // events' index
    for (int day = minDay; day < maxDay; ++day) {
      while (i < events.size() && events[i].day == day) {
        if (events[i].type == Type::kEntering)
          runningIndices.insert(events[i].index);
        else
          runningIndices.erase(events[i].index);
        ++i;
      }
      if (!runningIndices.empty())
        ++ans[*runningIndices.begin()];
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
enum Type { kEntering, kLeaving }

class Event {
  public int day;
  public int index;
  public Type type;
  public Event(int day, int index, Type type) {
    this.day = day;
    this.index = index;
    this.type = type;
  }
}

class Solution {
  public int[] amountPainted(int[][] paint) {
    final int n = paint.length;
    final int minDay = Arrays.stream(paint).mapToInt(x -> x[0]).min().getAsInt();
    final int maxDay = Arrays.stream(paint).mapToInt(x -> x[1]).max().getAsInt();
    int[] ans = new int[n];
    // Stores the indices of paints that are available now.
    TreeSet<Integer> runningIndices = new TreeSet<>();
    List<Event> events = new ArrayList<>();

    for (int i = 0; i < n; ++i) {
      final int start = paint[i][0];
      final int end = paint[i][1];
      events.add(new Event(start, i, Type.kEntering)); // 1 := entering
      events.add(new Event(end, i, Type.kLeaving));    // -1 := leaving
    }

    Collections.sort(events, (a, b) -> Integer.compare(a.day, b.day));

    int i = 0; // events' index
    for (int day = minDay; day < maxDay; ++day) {
      while (i < events.size() && events.get(i).day == day) {
        if (events.get(i).type == Type.kEntering)
          runningIndices.add(events.get(i).index);
        else
          runningIndices.remove(events.get(i).index);
        ++i;
      }
      if (!runningIndices.isEmpty())
        ++ans[runningIndices.first()];
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from sortedcontainers import SortedList


class Solution:
  def amountPainted(self, paint: list[list[int]]) -> list[int]:
    minDay = min(s for s, e in paint)
    maxDay = max(e for s, e in paint)
    ans = [0] * len(paint)
    # Stores the indices of paints that are available now.
    runningIndices = SortedList()
    events = []  # (day, index, type)

    for i, (start, end) in enumerate(paint):
      events.append((start, i, 1))  # 1 := entering
      events.append((end, i, -1))  # -1 := leaving

    events.sort()

    i = 0  # events' index
    for day in range(minDay, maxDay):
      while i < len(events) and events[i][0] == day:
        day, index, type = events[i]
        if type == 1:
          runningIndices.add(index)
        else:
          runningIndices.remove(index)
        i += 1
      if runningIndices:
        ans[runningIndices[0]] += 1

    return ans

Approach 2: Ordered Map

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  vector<int> amountPainted(vector<vector<int>>& paint) {
    map<int, int> intervals;
    vector<int> result;

    for (const vector<int>& p : paint) {
      int eraseLen = 0;
      auto it = intervals.lower_bound(p[0]);
      if (it != intervals.begin() && prev(it)->second >= p[0])
        --it;
      while (it != intervals.end() && p[1] >= it->first) {
        eraseLen += it->second - it->first;
        p[0] = min(p[0], it->first);
        p[1] = max(p[1], it->second);
        it = intervals.erase(it);
      }
      intervals.insert({p[0], p[1]});
      result.push_back(p[1] - p[0] - eraseLen);
    }

    return result;
  }
};