🧌Beginner-Friendly Guide "Maximize Value from Non-Overlapping Events with DP" – LeetCode 1751 (C++ | Python | JavaScript)

#programming #cpp #javascript #python

You're given a list of events, each defined by a start day, end day, and value. You can attend at most k events, and events cannot overlap (inclusive on end day). Your goal is to choose a combination of events to maximize the total value.

🧠 Intuition

This is a dynamic programming problem with sorting and binary search. The strategy involves:

Sorting the events by start day.
Using memoization to track the best value at each step.
For each event, choose to either:
- Skip it.
- Attend it and move to the next non-overlapping event.

The trick is efficiently finding the next non-overlapping event using binary search.

🚀 C++ Code

class Solution {
public:
    static uint32_t maxValue(const std::span<const std::vector<int>> in_events,
                             const uint32_t k) {

        const uint32_t num_events = in_events.size();

        struct Event {
            uint32_t start_time;
            uint32_t end_time;
            uint32_t value;
        };

        Event events[num_events];

        for (uint32_t i = 0; i < num_events; ++i) {
            const auto& event = in_events[i];
            events[i] = Event{uint32_t(event[0]) - 1u, uint32_t(event[1]),
                              uint32_t(event[2])};
        }

        std::sort(events, events + num_events,
                  [](const Event& l, const Event& r) {
                      return l.start_time < r.start_time;
                  });

        const uint32_t height = num_events + 1;
        const uint32_t width = k + 1;
        uint32_t table[width * height];

        for (uint32_t x = 0; x < width; ++x)
            table[x + (height - 1) * width] = 0;

        for (int y = height - 2; y >= 0; --y) {
            const Event& event = events[y];
            const uint32_t other_y =
                std::lower_bound(events + y + 1, events + num_events,
                                 event.end_time,
                                 [](const Event& l, const uint32_t r) {
                                     return l.start_time < r;
                                 }) - events;

            table[0 + y * width] = 0;

            for (uint32_t x = 1; x < width; ++x) {
                uint32_t max_value = std::max(table[x + (y + 1) * width],
                                             event.value + (other_y < num_events ? table[x - 1 + other_y * width] : 0));
                table[x + y * width] = max_value;
            }
        }

        return table[k + 0 * width];
    }
};

🐍 Python Code

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort()
        n = len(events)

        @lru_cache(None)
        def dp(i, rem):
            if i == n or rem == 0:
                return 0
            j = bisect.bisect_right(events, [events[i][1], float('inf'), float('inf')], i+1)
            return max(dp(i+1, rem), events[i][2] + dp(j, rem-1))

        return dp(0, k)

💻 JavaScript Code

var maxValue = function(events, k) {
    events.sort((a, b) => a[0] - b[0]);
    const n = events.length;
    const memo = new Map();

    const dp = (i, rem) => {
        if (i === n || rem === 0) return 0;
        const key = `${i},${rem}`;
        if (memo.has(key)) return memo.get(key);

        let lo = i + 1, hi = n;
        while (lo < hi) {
            const mid = Math.floor((lo + hi) / 2);
            if (events[mid][0] <= events[i][1]) lo = mid + 1;
            else hi = mid;
        }

        const res = Math.max(dp(i + 1, rem), events[i][2] + dp(lo, rem - 1));
        memo.set(key, res);
        return res;
    };

    return dp(0, k);
};