Skip to content

1751. Maximum Number of Events That Can Be Attended II

SourceBiweekly Contest 45 Q4DifficultyHardRating2040

Description

You are given an array of events where events[i] = [startDayi, endDayi, valuei]. The ith event starts at startDayi and ends at endDayi, and if you attend this event, you will receive a value of valuei. You are also given an integer k which represents the maximum number of events you can attend.

You can only attend one event at a time. If you choose to attend an event, you must attend the entire event. Note that the end day is inclusive: that is, you cannot attend two events where one of them starts and the other ends on the same day.

Return the maximum sum of values that you can receive by attending events.

 

Example 1:

Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
Output: 7
Explanation: Choose the green events, 0 and 1 (0-indexed) for a total value of 4 + 3 = 7.

Example 2:

Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
Output: 10
Explanation: Choose event 2 for a total value of 10.
Notice that you cannot attend any other event as they overlap, and that you do not have to attend k events.

Example 3:

Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
Output: 9
Explanation: Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.

 

Constraints:

  • 1 <= k <= events.length
  • 1 <= k * events.length <= 106
  • 1 <= startDayi <= endDayi <= 109
  • 1 <= valuei <= 106

Solutions

Thinking

Attend at most \(k\) non-overlapping events for maximum total value. After sorting by start time, we take or skip the current event and binary-search the next feasible one.

\(\textit{dfs}(i,k)\) is the best from event \(i\) with \(k\) slots left. Skipping goes to \(i+1\); taking binary-searches the first start after this end and adds the value. Memoize the states.

First, we sort the events by their start time in ascending order. Then, we define a function \(\text{dfs}(i, k)\), which represents the maximum total value achievable by attending at most \(k\) events starting from the \(i\)-th event. The answer is \(\text{dfs}(0, k)\).

The calculation process of the function \(\text{dfs}(i, k)\) is as follows:

If we do not attend the \(i\)-th event, the maximum value is \(\text{dfs}(i + 1, k)\). If we attend the \(i\)-th event, we can use binary search to find the first event whose start time is greater than the end time of the \(i\)-th event, denoted as \(j\). Then, the maximum value is \(\text{dfs}(j, k - 1) + \text{value}[i]\). We take the maximum of the two options:

\[ \text{dfs}(i, k) = \max(\text{dfs}(i + 1, k), \text{dfs}(j, k - 1) + \text{value}[i]) \]

Here, \(j\) is the index of the first event whose start time is greater than the end time of the \(i\)-th event, which can be found using binary search.

Since the calculation of \(\text{dfs}(i, k)\) involves calls to \(\text{dfs}(i + 1, k)\) and \(\text{dfs}(j, k - 1)\), we can use memoization to store the computed values and avoid redundant calculations.

The time complexity is \(O(n \times \log n + n \times k)\), and the space complexity is \(O(n \times k)\), where \(n\) is the number of events.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        @cache
        def dfs(i: int, k: int) -> int:
            if i >= len(events):
                return 0
            _, ed, val = events[i]
            ans = dfs(i + 1, k)
            if k:
                j = bisect_right(events, ed, lo=i + 1, key=lambda x: x[0])
                ans = max(ans, dfs(j, k - 1) + val)
            return ans

        events.sort()
        return dfs(0, 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
36
37
38
class Solution {
    private int[][] events;
    private int[][] f;
    private int n;

    public int maxValue(int[][] events, int k) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        this.events = events;
        n = events.length;
        f = new int[n][k + 1];
        return dfs(0, k);
    }

    private int dfs(int i, int k) {
        if (i >= n || k <= 0) {
            return 0;
        }
        if (f[i][k] != 0) {
            return f[i][k];
        }
        int j = search(events, events[i][1], i + 1);
        int ans = Math.max(dfs(i + 1, k), dfs(j, k - 1) + events[i][2]);
        return f[i][k] = ans;
    }

    private int search(int[][] events, int x, int lo) {
        int l = lo, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (events[mid][0] > x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

 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
class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        ranges::sort(events);
        int n = events.size();
        int f[n][k + 1];
        memset(f, 0, sizeof(f));
        auto dfs = [&](this auto&& dfs, int i, int k) -> int {
            if (i >= n || k <= 0) {
                return 0;
            }
            if (f[i][k] > 0) {
                return f[i][k];
            }

            int ed = events[i][1], val = events[i][2];
            vector<int> t = {ed};

            int p = upper_bound(events.begin() + i + 1, events.end(), t,
                        [](const auto& a, const auto& b) { return a[0] < b[0]; })
                - events.begin();

            f[i][k] = max(dfs(i + 1, k), dfs(p, k - 1) + val);
            return f[i][k];
        };

        return dfs(0, k);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func maxValue(events [][]int, k int) int {
    sort.Slice(events, func(i, j int) bool { return events[i][0] < events[j][0] })
    n := len(events)
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, k+1)
    }
    var dfs func(i, k int) int
    dfs = func(i, k int) int {
        if i >= n || k <= 0 {
            return 0
        }
        if f[i][k] > 0 {
            return f[i][k]
        }
        j := sort.Search(n, func(h int) bool { return events[h][0] > events[i][1] })
        ans := max(dfs(i+1, k), dfs(j, k-1)+events[i][2])
        f[i][k] = ans
        return ans
    }
    return dfs(0, 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
function maxValue(events: number[][], k: number): number {
    events.sort((a, b) => a[0] - b[0]);
    const n = events.length;
    const f: number[][] = Array.from({ length: n }, () => Array(k + 1).fill(0));

    const dfs = (i: number, k: number): number => {
        if (i >= n || k <= 0) {
            return 0;
        }
        if (f[i][k] > 0) {
            return f[i][k];
        }

        const ed = events[i][1],
            val = events[i][2];

        let left = i + 1,
            right = n;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (events[mid][0] > ed) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        const p = left;

        f[i][k] = Math.max(dfs(i + 1, k), dfs(p, k - 1) + val);
        return f[i][k];
    };

    return dfs(0, 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
36
impl Solution {
    pub fn max_value(mut events: Vec<Vec<i32>>, k: i32) -> i32 {
        events.sort_by_key(|e| e[0]);
        let n = events.len();
        let mut f = vec![vec![0; (k + 1) as usize]; n];

        fn dfs(i: usize, k: i32, events: &Vec<Vec<i32>>, f: &mut Vec<Vec<i32>>, n: usize) -> i32 {
            if i >= n || k <= 0 {
                return 0;
            }
            if f[i][k as usize] != 0 {
                return f[i][k as usize];
            }
            let j = search(events, events[i][1], i + 1, n);
            let ans = dfs(i + 1, k, events, f, n).max(dfs(j, k - 1, events, f, n) + events[i][2]);
            f[i][k as usize] = ans;
            ans
        }

        fn search(events: &Vec<Vec<i32>>, x: i32, lo: usize, n: usize) -> usize {
            let mut l = lo;
            let mut r = n;
            while l < r {
                let mid = (l + r) / 2;
                if events[mid][0] > x {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            l
        }

        dfs(0, k, &events, &mut f, n)
    }
}

Thinking

Solution 1 sorts by start and fills a suffix table. Sorting by end instead, \(f[i][j]\) is the best using the first \(i\) events and \(j\) slots, binary-searching the last non-conflicting event.

Solution 1 sorts by start and fills a suffix table. Here we sort by end and define a prefix table.

First, sort the events, this time by end time in ascending order. Then define \(f[i][j]\) as the maximum total value by attending at most \(j\) events among the first \(i\) events. The answer is \(f[n][k]\).

For the \(i\)-th event, we can choose to attend it or not. If we do not attend, the maximum value is \(f[i][j]\). If we attend, we can use binary search to find the last event whose end time is less than the start time of the \(i\)-th event, denoted as \(h\). Then the maximum value is \(f[h + 1][j - 1] + \text{value}[i]\). We take the maximum of the two options:

\[ f[i + 1][j] = \max(f[i][j], f[h + 1][j - 1] + \text{value}[i]) \]

Here, \(h\) is the last event whose end time is less than the start time of the \(i\)-th event, which can be found by binary search.

The time complexity is \(O(n \times \log n + n \times k)\), and the space complexity is \(O(n \times k)\), where \(n\) is the number of events.

Related problems:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort(key=lambda x: x[1])
        n = len(events)
        f = [[0] * (k + 1) for _ in range(n + 1)]
        for i, (st, _, val) in enumerate(events, 1):
            p = bisect_left(events, st, hi=i - 1, key=lambda x: x[1])
            for j in range(1, k + 1):
                f[i][j] = max(f[i - 1][j], f[p][j - 1] + val)
        return f[n][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
class Solution {
    public int maxValue(int[][] events, int k) {
        Arrays.sort(events, (a, b) -> a[1] - b[1]);
        int n = events.length;
        int[][] f = new int[n + 1][k + 1];
        for (int i = 1; i <= n; ++i) {
            int st = events[i - 1][0], val = events[i - 1][2];
            int p = search(events, st, i - 1);
            for (int j = 1; j <= k; ++j) {
                f[i][j] = Math.max(f[i - 1][j], f[p][j - 1] + val);
            }
        }
        return f[n][k];
    }

    private int search(int[][] events, int x, int hi) {
        int l = 0, r = hi;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (events[mid][1] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        sort(events.begin(), events.end(), [](const auto& a, const auto& b) { return a[1] < b[1]; });
        int n = events.size();
        int f[n + 1][k + 1];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; ++i) {
            int st = events[i - 1][0], val = events[i - 1][2];
            vector<int> t = {st};
            int p = lower_bound(events.begin(), events.begin() + i - 1, t, [](const auto& a, const auto& b) { return a[1] < b[0]; }) - events.begin();
            for (int j = 1; j <= k; ++j) {
                f[i][j] = max(f[i - 1][j], f[p][j - 1] + val);
            }
        }
        return f[n][k];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func maxValue(events [][]int, k int) int {
    sort.Slice(events, func(i, j int) bool { return events[i][1] < events[j][1] })
    n := len(events)
    f := make([][]int, n+1)
    for i := range f {
        f[i] = make([]int, k+1)
    }
    for i := 1; i <= n; i++ {
        st, val := events[i-1][0], events[i-1][2]
        p := sort.Search(i, func(j int) bool { return events[j][1] >= st })
        for j := 1; j <= k; j++ {
            f[i][j] = max(f[i-1][j], f[p][j-1]+val)
        }
    }
    return f[n][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
function maxValue(events: number[][], k: number): number {
    events.sort((a, b) => a[1] - b[1]);
    const n = events.length;
    const f: number[][] = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0));
    const search = (x: number, hi: number): number => {
        let l = 0;
        let r = hi;
        while (l < r) {
            const mid = (l + r) >> 1;
            if (events[mid][1] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    };
    for (let i = 1; i <= n; ++i) {
        const [st, _, val] = events[i - 1];
        const p = search(st, i - 1);
        for (let j = 1; j <= k; ++j) {
            f[i][j] = Math.max(f[i - 1][j], f[p][j - 1] + val);
        }
    }
    return f[n][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
impl Solution {
    pub fn max_value(mut events: Vec<Vec<i32>>, k: i32) -> i32 {
        events.sort_by_key(|e| e[1]);
        let n = events.len();
        let mut f = vec![vec![0; (k + 1) as usize]; n + 1];

        for i in 1..=n {
            let st = events[i - 1][0];
            let val = events[i - 1][2];
            let p = search(&events, st, i - 1);
            for j in 1..=k as usize {
                f[i][j] = f[i - 1][j].max(f[p][j - 1] + val);
            }
        }

        f[n][k as usize]
    }
}

fn search(events: &Vec<Vec<i32>>, x: i32, hi: usize) -> usize {
    let mut l = 0;
    let mut r = hi;
    while l < r {
        let mid = (l + r) / 2;
        if events[mid][1] >= x {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    l
}

Thinking

Attend at most \(k\) non-overlapping events for maximum total value. \(k \times n \le 10^6\), so \(n\) itself can be \(10^6\) and listing subsets is impossible.

After sorting by start, skipping calls \(i+1\) with the same remaining slots before it returns, so the chain has length \(n\) and overflows the stack.

Later events and a smaller slot count are known if we walk backward. Let \(f[i][c]\) be the best value from event \(i\) with \(c\) slots left, and fill \(i\) from \(n-1\) down to \(0\).

First, we sort the events by their start time in ascending order. Let \(f[i][c]\) be the maximum total value achievable by attending at most \(c\) events starting from the \(i\)-th event. The answer is \(f[0][k]\), and \(f[n][c] = 0\).

Fill \(i\) from \(n - 1\) down to \(0\). If we do not attend the \(i\)-th event, the maximum value is \(f[i + 1][c]\). If \(c > 0\) and we attend it, binary search finds the first event \(j\) whose start time is greater than the end time of the \(i\)-th event. The value is then \(f[j][c - 1] + \text{value}[i]\). Take the larger of the two:

\[ f[i][c] = \max(f[i + 1][c], f[j][c - 1] + \text{value}[i]) \]

Here, \(j\) is the index of the first event whose start time is greater than the end time of the \(i\)-th event. Because \(j > i\), \(f[j]\) is already filled.

The time complexity is \(O(n \times \log n + n \times k)\), and the space complexity is \(O(n \times k)\), where \(n\) is the number of events.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort()
        n = len(events)
        f = [[0] * (k + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            _, ed, val = events[i]
            j = bisect_right(events, ed, lo=i + 1, key=lambda x: x[0])
            for c in range(k + 1):
                f[i][c] = f[i + 1][c]
                if c:
                    f[i][c] = max(f[i][c], f[j][c - 1] + val)
        return f[0][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
class Solution {
    public int maxValue(int[][] events, int k) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        int n = events.length;
        int[][] f = new int[n + 1][k + 1];
        for (int i = n - 1; i >= 0; --i) {
            int ed = events[i][1], val = events[i][2];
            int j = search(events, ed, i + 1);
            for (int c = 0; c <= k; ++c) {
                f[i][c] = f[i + 1][c];
                if (c > 0) {
                    f[i][c] = Math.max(f[i][c], f[j][c - 1] + val);
                }
            }
        }
        return f[0][k];
    }

    private int search(int[][] events, int x, int lo) {
        int l = lo, r = events.length;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (events[mid][0] > x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        ranges::sort(events);
        int n = events.size();
        vector<vector<int>> f(n + 1, vector<int>(k + 1));
        for (int i = n - 1; i >= 0; --i) {
            int ed = events[i][1], val = events[i][2];
            vector<int> t = {ed};
            int p = upper_bound(events.begin() + i + 1, events.end(), t, [](const auto& a, const auto& b) { return a[0] < b[0]; }) - events.begin();
            for (int c = 0; c <= k; ++c) {
                f[i][c] = f[i + 1][c];
                if (c) {
                    f[i][c] = max(f[i][c], f[p][c - 1] + val);
                }
            }
        }
        return f[0][k];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func maxValue(events [][]int, k int) int {
    sort.Slice(events, func(i, j int) bool { return events[i][0] < events[j][0] })
    n := len(events)
    f := make([][]int, n+1)
    for i := range f {
        f[i] = make([]int, k+1)
    }
    for i := n - 1; i >= 0; i-- {
        ed, val := events[i][1], events[i][2]
        j := sort.Search(n, func(h int) bool { return events[h][0] > ed })
        for c := 0; c <= k; c++ {
            f[i][c] = f[i+1][c]
            if c > 0 {
                f[i][c] = max(f[i][c], f[j][c-1]+val)
            }
        }
    }
    return f[0][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
function maxValue(events: number[][], k: number): number {
    events.sort((a, b) => a[0] - b[0]);
    const n = events.length;
    const f: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
    const search = (ed: number, lo: number): number => {
        let left = lo;
        let right = n;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (events[mid][0] > ed) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    };
    for (let i = n - 1; i >= 0; --i) {
        const ed = events[i][1],
            val = events[i][2];
        const p = search(ed, i + 1);
        for (let c = 0; c <= k; ++c) {
            f[i][c] = f[i + 1][c];
            if (c > 0) {
                f[i][c] = Math.max(f[i][c], f[p][c - 1] + val);
            }
        }
    }
    return f[0][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
impl Solution {
    pub fn max_value(mut events: Vec<Vec<i32>>, k: i32) -> i32 {
        events.sort_by_key(|e| e[0]);
        let n = events.len();
        let kk = k as usize;
        let mut f = vec![vec![0; kk + 1]; n + 1];
        for i in (0..n).rev() {
            let ed = events[i][1];
            let val = events[i][2];
            let p = search(&events, ed, i + 1, n);
            for c in 0..=kk {
                f[i][c] = f[i + 1][c];
                if c > 0 {
                    f[i][c] = f[i][c].max(f[p][c - 1] + val);
                }
            }
        }
        f[0][kk]
    }
}

fn search(events: &Vec<Vec<i32>>, x: i32, lo: usize, n: usize) -> usize {
    let mut l = lo;
    let mut r = n;
    while l < r {
        let mid = (l + r) / 2;
        if events[mid][0] > x {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    l
}

Comments