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
class Solution {
 public:
  int maxValue(vector<vector<int>>& events, int k) {
    // dp[i][k] := the maximum the sum of events[i:] with max k # of attendance
    dp.resize(events.size(), vector<int>(k + 1, -1));
    ranges::sort(events);
    return maxValue(events, 0, k);
  }

 private:
  vector<vector<int>> dp;

  int maxValue(const vector<vector<int>>& e, int i, int k) {
    if (k == 0 || i == e.size())
      return 0;
    if (dp[i][k] != -1)
      return dp[i][k];

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

 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
class Solution {
  public int maxValue(int[][] events, int k) {
    // dp[i][k] := the maximum the sum of events[i:] with max k # of attendance
    dp = 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);
  }

  private Integer[][] dp;

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

    final int j = binarySearch(e, i + 1, e[i][1] + 1);
    return dp[i][k] = Math.max(e[i][2] + maxValue(e, j, k - 1), maxValue(e, i + 1, k));
  }

  // Find the first index l s.t e[l][0] >= target
  private int binarySearch(int[][] e, int l, int target) {
    int r = e.length;

    while (l < r) {
      final int m = (l + r) / 2;
      if (e[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
class Solution:
  def maxValue(self, events: List[List[int]], k: int) -> int:
    e = sorted(events)

    @functools.lru_cache(None)
    def dp(i, k):
      if k == 0 or i == len(e):
        return 0

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

    return dp(0, k)