4068. Maximize Meeting Earnings with Idle Gaps

DifficultyHard

Description

You are given a 2D integer array meetings, where meetings[i] = [start_i, end_i, revenue_i] represents a meeting starting at time start_i, ending at time end_i, with revenue revenue_i.

All meetings use half-open intervals [start, end), so meetings that only touch at endpoints do not overlap.

You may select any non-empty subset of meetings such that no two selected meetings overlap. You earn the revenue of each selected meeting.

Arrange the selected meetings in increasing order of their start times. For each pair of adjacent meetings in this order, you also earn 1 unit of revenue per unit of idle time between them. This idle time equals the later meeting's start time minus the earlier meeting's end time.

No idle revenue is earned before the earliest selected meeting starts or after the latest selected meeting ends. If only one meeting is selected, no idle revenue is earned.

Return the maximum total earnings achievable.

A subset of an array is a selection of elements of the array.

Example 1:

Input: meetings = [[2,5,4],[6,8,3]]

Output: 8

Explanation:

Select both meetings. They do not overlap and earn 4 + 3 = 7 units of meeting revenue.
The first meeting ends at time 5, and the second starts at time 6. This idle gap earns 6 - 5 = 1 additional unit.
The maximum total earnings are 7 + 1 = 8.

Example 2:

Input: meetings = [[3,5,4],[4,7,8],[8,10,3]]

Output: 12

Explanation:

Select the meetings at indices 1 and 2. They do not overlap and earn 8 + 3 = 11 units of meeting revenue.
In chronological order, these meetings run from time 4 to 7 and from time 8 to 10. The idle gap earns 8 - 7 = 1 additional unit.
The maximum total earnings are 11 + 1 = 12.

Example 3:

Input: meetings = [[1,2,2],[4,5,2],[7,9,3]]

Output: 11

Explanation:

Select all three meetings. They do not overlap and earn 2 + 2 + 3 = 7 units of meeting revenue.
The idle gap from time 2 to 4 earns 4 - 2 = 2 additional units.
The idle gap from time 5 to 7 earns 7 - 5 = 2 additional units.
The maximum total earnings are 7 + 2 + 2 = 11.

Constraints

1 <= meetings.length <= 10⁵
meetings[i] = [start_i, end_i, revenue_i]
0 <= start_i < end_i <= 10⁹
1 <= revenue_i <= 10⁹

Solutions

Solution 1: Sort, Binary Search, and DP

Thinking

There can be \(10^5\) meetings, so enumerating subsets does not work. Earnings come from two parts: the revenue of each selected meeting, and the idle gap between meetings that are adjacent after sorting by start time. A single meeting earns no idle revenue.

Fix one meeting as the last meeting of a schedule. Every meeting placed before it must end no later than its start, and the new gap is \(\textit{start}\) minus that previous end. The quantity to maximize is therefore the best earnings of a schedule ending at a meeting, minus that meeting's end time.

After sorting by end time, the meetings that can precede the current one form a prefix, and the prefix maximum can be located by binary search. Revenues and gaps are accumulated in \(64\)-bit integers.

Sort the meetings by ascending end time. Let \(f[i]\) be the maximum earnings of a schedule whose last meeting is meeting \(i\). Every non-empty schedule has a meeting that ends last, so the answer is the maximum of all \(f[i]\).

Selecting meeting \(i\) alone gives \(f[i]=\textit{revenue}_i\). If a meeting \(j\) with \(\textit{end}_j\le\textit{start}_i\) is placed before it, then

\[ f[i]=f[j]+\textit{revenue}_i+(\textit{start}_i-\textit{end}_j), \]

which rearranges to

\[ f[i]=\textit{revenue}_i+\textit{start}_i+\max_j(f[j]-\textit{end}_j). \]

After the sort, those indices \(j\) form a prefix. Let

\[ \textit{preMax}[k]=\max_{j<k}(f[j]-\textit{end}_j), \]

using a sentinel while no meeting has been processed. When handling meeting \(i\), binary-search the first index \(p\) in \([0,i)\) whose end time is greater than \(\textit{start}_i\). Then \(\textit{preMax}[p]\) is the maximum above. If \(\textit{start}_i\) is smaller than the earliest end time, the prefix is empty and meeting \(i\) must be taken alone.

Then set \(\textit{preMax}[i+1]=\max(\textit{preMax}[i], f[i]-\textit{end}_i)\). Two meetings with the same end time overlap, so the binary search does not chain them.

The time complexity is \(O(n\log n)\) and the space complexity is \(O(n)\).

Python3JavaC++GoTypeScript

class Solution:
    def maxEarnings(self, meetings: list[list[int]]) -> int:
        n = len(meetings)
        meetings.sort(key=lambda x: x[1])

        pre_max = [-inf] * (n + 1)
        ans = 0

        for i, (start, end, revenue) in enumerate(meetings):
            val = revenue
            if start >= meetings[0][1]:
                j = bisect_right(meetings, start, hi=i, key=lambda x: x[1])
                val += pre_max[j] + start

            ans = max(ans, val)
            pre_max[i + 1] = max(pre_max[i], val - end)

        return ans

class Solution {
    public long maxEarnings(int[][] meetings) {
        int n = meetings.length;
        Arrays.sort(meetings, (a, b) -> a[1] - b[1]);

        long[] preMax = new long[n + 1];
        Arrays.fill(preMax, Long.MIN_VALUE / 2);

        long ans = 0;

        for (int i = 0; i < n; i++) {
            int start = meetings[i][0];
            int end = meetings[i][1];
            int revenue = meetings[i][2];

            long val = revenue;
            if (start >= meetings[0][1]) {
                int j = upperBound(meetings, start, i);
                val += preMax[j] + start;
            }

            ans = Math.max(ans, val);
            preMax[i + 1] = Math.max(preMax[i], val - end);
        }

        return ans;
    }

    private int upperBound(int[][] meetings, int target, int hi) {
        int l = 0, r = hi;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (meetings[m][1] <= target) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }
}

class Solution {
public:
    long long maxEarnings(vector<vector<int>>& meetings) {
        int n = meetings.size();
        sort(meetings.begin(), meetings.end(), [](auto& a, auto& b) {
            return a[1] < b[1];
        });

        vector<long long> preMax(n + 1, LLONG_MIN / 2);
        long long ans = 0;

        for (int i = 0; i < n; i++) {
            int start = meetings[i][0];
            int end = meetings[i][1];
            int revenue = meetings[i][2];

            long long val = revenue;
            if (start >= meetings[0][1]) {
                int j = upper_bound(meetings.begin(), meetings.begin() + i, start,
                            [](int x, const vector<int>& y) {
                                return x < y[1];
                            })
                    - meetings.begin();
                val += preMax[j] + start;
            }

            ans = max(ans, val);
            preMax[i + 1] = max(preMax[i], val - end);
        }

        return ans;
    }
};

func maxEarnings(meetings [][]int) int64 {
    n := len(meetings)
    sort.Slice(meetings, func(i, j int) bool {
        return meetings[i][1] < meetings[j][1]
    })

    preMax := make([]int64, n+1)
    for i := range preMax {
        preMax[i] = -1 << 60
    }

    var ans int64

    for i, meeting := range meetings {
        start, end, revenue := meeting[0], meeting[1], meeting[2]

        val := int64(revenue)
        if start >= meetings[0][1] {
            j := sort.Search(i, func(j int) bool {
                return meetings[j][1] > start
            })
            val += preMax[j] + int64(start)
        }

        ans = max(ans, val)
        preMax[i+1] = max(preMax[i], val-int64(end))
    }

    return ans
}

function maxEarnings(meetings: number[][]): number {
    const n = meetings.length;
    meetings.sort((a, b) => a[1] - b[1]);

    const preMax = new Array<number>(n + 1).fill(-Infinity);
    let ans = 0;

    for (let i = 0; i < n; i++) {
        const start = meetings[i][0];
        const end = meetings[i][1];
        const revenue = meetings[i][2];

        let val = revenue;
        if (start >= meetings[0][1]) {
            let l = 0;
            let r = i;
            while (l < r) {
                const m = (l + r) >> 1;
                if (meetings[m][1] <= start) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
            val += preMax[l] + start;
        }

        ans = Math.max(ans, val);
        preMax[i + 1] = Math.max(preMax[i], val - end);
    }

    return ans;
}

4068. Maximize Meeting Earnings with Idle Gaps

Description

Constraints

Solutions

Solution 1: Sort, Binary Search, and DP

Comments