Skip to content

1751. Maximum Number of Events That Can Be Attended II 👍

  • Time: $O(nk\log n)$
  • Space: $O(nk)$
 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
class Solution {
 public:
  int maxValue(vector<vector<int>>& events, int k) {
    vector<vector<int>> mem(events.size(), vector<int>(k + 1, -1));
    ranges::sort(events);
    return maxValue(events, 0, k, mem);
  }

 private:
  // Returns the maximum sum of values that you can receive by attending
  // events[i..n), where k is the maximum number of attendancevents.
  int maxValue(const vector<vector<int>>& events, int i, int k,
               vector<vector<int>>& mem) {
    if (k == 0 || i == events.size())
      return 0;
    if (mem[i][k] != -1)
      return mem[i][k];

    // Binary search `events` to find the first index j
    // s.t. events[j][0] > events[i][1].
    const auto it = upper_bound(
        events.begin() + i, events.end(), events[i][1],
        [](int end, const vector<int>& event) { return event[0] > end; });
    const int j = distance(events.begin(), it);
    return mem[i][k] = max(events[i][2] + maxValue(events, j, k - 1, mem),
                           maxValue(events, i + 1, k, mem));
  }
};

 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
class Solution {
  public int maxValue(int[][] events, int k) {
    Integer[][] mem = new Integer[events.length][k + 1];
    Arrays.sort(events, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    return maxValue(events, 0, k, mem);
  }

  private int maxValue(int[][] events, int i, int k, Integer[][] mem) {
    if (k == 0 || i == events.length)
      return 0;
    if (mem[i][k] != null)
      return mem[i][k];

    // Binary search `events` to find the first index j
    // s.t. events[j][0] > events[i][1].
    final int j = firstGreaterEqual(events, i + 1, events[i][1] + 1);
    return mem[i][k] = Math.max(events[i][2] + maxValue(events, j, k - 1, mem),
                                maxValue(events, i + 1, k, mem));
  }

  // Finds the first index l s.t events[l][0] >= target.
  private int firstGreaterEqual(int[][] events, int l, int target) {
    int r = events.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if (events[m][0] >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def maxValue(self, events: List[List[int]], k: int) -> int:
    events.sort()

    @functools.lru_cache(None)
    def dp(i: int, k: int) -> int:
      """
      Returns the maximum sum of values that you can receive by attending
      events[i..n), where k is the maximum number of attendance.
      """
      if k == 0 or i == len(events):
        return 0

      # Binary search `events` to find the first index j
      # s.t. events[j][0] > events[i][1].
      j = bisect.bisect(events, [events[i][1], math.inf, math.inf], i + 1)
      return max(events[i][2] + dp(j, k - 1), dp(i + 1, k))

    return dp(0, k)