This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 1751 on LeetCode. Maximum number of meetings that can be attended II, difficulty is difficult.

Tag: “dichotomy”, “linear DP”

Events [I] = [startDayi, endDayi, valuei]; events[I] = [startDayi, endDayi, valuei]; events[I] = [startDayi, endDayi, valuei]; You get valuei.

You are also given an integer k for the maximum number of meetings you can attend.

You can only attend one meeting at a time. If you choose to attend a meeting, you must attend the entire meeting.

The meeting end date is included in the meeting, which means you cannot attend two meetings with the same start date and the same end date.

Please return the maximum value you can get from the session and.

Example 1:

Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2 Output: 7 Explanation: select green event 0 and 1 to get the total value of 4 + 3 = 7.Copy the code

Example 2:

Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2 You can't go to another meeting because it overlaps with Meeting 2. You don't have to attend all k meetings.Copy the code

Example 3:

Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4]], k = 3 output: 9 explanation: although meetings do not overlap, you can only attend 3 meetings, so choose the 3 meetings with the highest value.Copy the code

Tip:

  • 1 <= k <= events.length
  • 1 <= k * events.length <=
    1 0 6 10^6
  • 1 <= startDayi <= endDayi <=
    1 0 9 10^9
  • 1 <= valuei <=
    1 0 6 10^6

The basic idea

F [I][j] is defined as the maximum value of j not exceeding the I times before consideration

For each piece of time, there are two choices: select and do not select, do not select f[I][j] = F [i-1][j].

In this case, it is necessary to find the event before the ith event that does not conflict with the ith event, denoted as last, then f[I][j] = f[last][J-1].

The value of f[I][j].

At this point, because we want to find last, we need to sort the end time of events first, and then look from right to left to find the first event whose end time is less than the start time of the current event, which is last

And the process of finding last, can be found directly cycle, can also be found through dichotomy, can pass.

Dynamic programming

Find the DP solution of last without “dichotomy”.

Code:

class Solution {
    public int maxValue(int[][] es, int k) {
        int n = es.length;
        Arrays.sort(es, (a, b)->a[1]-b[1]);
        int[][] f = new int[n + 1][k + 1]; // f[I][j] represents the maximum value of j, considering the previous I events
        for (int i = 1; i <= n; i++) {
            int[] ev = es[i - 1];
            int s = ev[0], e = ev[1], v = ev[2];
            
            // The event that does not conflict with the i-th event before the i-th event is found
            // For the current event, the conflict is irrelevant to j
            int last = 0;
            for (int p = i - 1; p >= 1; p--) {
                int[] prev = es[p - 1];
                if (prev[1] < s) {
                    last = p;
                    break; }}for (int j = 1; j <= k; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[last][j - 1] + v); }}returnf[n][k]; }}Copy the code
  • Time complexity: Sort complexity is
    O ( n log ⁡ n ) O(n\log{n})     , the loopnZero events, and each time the loop needs to find one event back, the complexity is zero
    O ( n ) O(n)     And updatekAnd the complexity is
    O ( k ) O(k)     , so the complexity of the transfer is
    O ( n ∗ ( n + k ) ) O(n * (n + k))     ; The total complexity is
    O ( n ∗ ( n + k + log ⁡ n ) ) O(n * (n + k + \log{n}))
  • Space complexity: O(n∗k)O(n * k)O(n∗k)

Binary + dynamic programming

Find the DP solution of last by dichotomy.

Code:

class Solution {
    public int maxValue(int[][] es, int k) {
        int n = es.length;
        Arrays.sort(es, (a, b)->a[1]-b[1]);
        int[][] f = new int[n + 1][k + 1]; // f[I][j] represents the maximum value of j, considering the previous I events
        for (int i = 1; i <= n; i++) {
            int[] ev = es[i - 1];
            int s = ev[0], e = ev[1], v = ev[2];
            
            // Find the event that does not conflict with the i-th event before the i-th event by "dichotomy"
            // For the current event, the conflict is irrelevant to j
            int l = 1, r = i - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                int[] prev = es[mid - 1];
                if (prev[1] < s) {
                    l = mid;
                } else {
                    r = mid - 1; }}int last = (r > 0 && es[r - 1] [1] < s) ? r : 0;
            
            for (int j = 1; j <= k; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[last][j - 1] + v); }}returnf[n][k]; }}Copy the code
  • Time complexity: Sort complexity is
    O ( n log ⁡ n ) O(n\log{n})     , the loopnZero events, and each time the loop needs to find one event back, the complexity is zero
    O ( log ⁡ n ) O(\log{n})     And updatekAnd the complexity is
    O ( k ) O(k)     , so the complexity of the transfer is
    O ( n ∗ ( log ⁡ n + k ) ) O(n * (\log{n} + k))     ; The total complexity is
    O ( n ∗ ( k + log ⁡ n ) ) O(n * (k + \log{n}))
  • Space complexity: O(n∗k)O(n * k)O(n∗k)

The last

This is the No.1751 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.