Maximum Number of Events That Can Be Attended II

Problem Id: 1751 Difficulty: Hard Tag: Binary Search Tag: Dynamic Programming


Intuition

This problem is a typical DP problem.

The basic for any day which some events ended at that day. dp[end][count] = min(dp[start - 1][count - 1] + value. Where start and end are any of the jobs ended at the day end. count is the number of jobs and value is the value of the new job.

The time complexity is O(days * count). So here comes a new problem.

In the solution, because the start and end day could be 10**9, but the number of total events are only less than 10**6. We use a mapping to convert any possible start and end day to some number less than 10**6.

Solution


from collections import defaultdict


class Solution:
    def maxValue(self, events, k) -> int:
        candidates = sorted(set([i[0] for i in events] + [i[1] for i in events]))
        mapping = {v: i + 1 for i, v in enumerate(candidates)}
        events = [(mapping[i], mapping[j], k) for i, j, k in events]

        events_by_end_of_day = defaultdict(list)
        for event in events:
            events_by_end_of_day[event[1]].append(event)

        days = len(mapping)
        dp = [[0] * (k + 1) for _ in range(days + 1)]

        for end in range(1, days + 1):
            for count in range(1, k + 1):
                dp[end][count] = dp[end - 1][count]
                for start, _, value in events_by_end_of_day[end]:
                    dp[end][count] = max(
                        dp[end][count],
                        dp[start - 1][count - 1] + value
                    )

        return max(dp[-1])