Maximize Meeting Earnings with Idle Gaps solution and explanation
2 more videos on this problem
Leetcode 4068 | Maximize Meeting Earnings with Idle Gaps | Dynamic Programming | weekly contest 521CodeWithMeGuys · 16:48 · 191 views
4068. Maximize Meeting Earnings with Idle Gaps (Leetcode Hard)Programming Live with Larry · 17:12 · 165 views
LeetCode 4068 | Maximize Meeting Earnings with Idle Gaps | Java | HindiCode Kage · 32:22 · 92 views
The problem
You are given a 2D integer array meetings, where meetings[i] = [starti, endi, revenuei] represents a meeting starting at time starti, ending at time endi, with revenue revenuei.
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 = 7units of meeting revenue. - The first meeting ends at time 5, and the second starts at time 6. This idle gap earns
6 - 5 = 1additional 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 = 11units 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 = 1additional 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 = 7units of meeting revenue. - The idle gap from time 2 to 4 earns
4 - 2 = 2additional units. - The idle gap from time 5 to 7 earns
7 - 5 = 2additional units. - The maximum total earnings are
7 + 2 + 2 = 11.
Constraints
1 <= meetings.length <= 105meetings[i] = [starti, endi, revenuei]0 <= starti < endi <= 1091 <= revenuei <= 109
Approach overview
Problem Overview: You get a list of meetings, each with a time window and an earnings value. You choose a subset to attend, subject to the idle gap rule, and want the maximum total earnings. The core difficulty is that choosing one meeting constrains which others you can take, so greedy choices fail.
Approach 1: Recursive Include/Exclude (O(2^n) time, O(n) space)
Sort meetings by end time. For each meeting, branch into two choices: skip it, or take it and jump to the next meeting that respects the idle gap. This brute force enumerates every valid subset. It is correct but explodes exponentially because the same suffix states get recomputed many times. Use it to prove you understand the constraint, not as a final answer.
Approach 2: Bottom-Up DP With Linear Scan (O(n^2) time, O(n) space)
Sort meetings by end time and define dp[i] as the best earnings using only the first i meetings. For each meeting i, dp[i] = max(dp[i-1], earnings[i] + dp[j]), where j is the last meeting compatible with i. Find j by scanning backward. This removes the exponential blow-up, but the scan makes it quadratic. It is a good intermediate step if you are deriving the recurrence under time pressure.
Approach 3: Sort, Binary Search, and DP (O(n log n) time, O(n) space)
This is the optimal solution. Sort meetings by end time, and precompute each meeting's end times in a separate sorted array. For each meeting i, use binary search to find the rightmost meeting whose end time satisfies the idle gap requirement with the start of meeting i. Then run the same DP recurrence, but replace the linear scan with that binary search lookup. Sorting costs O(n log n), and the n binary searches cost O(n log n), so the total is O(n log n). The DP table is O(n). Prefer this approach whenever n can reach around 10^5, which is typical for this class of problem on the Dynamic Programming and Binary Search topics.
Recommended for interviews: Interviewers expect Approach 3. The brute force shows you understand the state space and the include/exclude tradeoff. The DP with linear scan shows you can derive the recurrence. The binary search optimization shows you can turn a quadratic bottleneck into an O(n log n) solution, which is the skill that separates strong candidates. Explain the sort step first, because the whole solution depends on processing meetings in a valid order. Also review Sorting if your sort comparator is not second nature.
Solution
Thinking
There can be
10^5meetings, 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
startminus 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]=revenue_i. If a meeting j with end_j\lestart_i is placed before it, then
$
f[i]=f[j]+revenue_i+(start_i-end_j),
which rearranges to
f[i]=revenue_i+start_i+max_j(f[j]-end_j).
After the sort, those indices j form a prefix. Let
preMax[k]=max_{j<k}(f[j]-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 start_i. Then preMax[p] is the maximum above. If start_i is smaller than the earliest end time, the prefix is empty and meeting i must be taken alone.
Then set preMax[i+1]=max(preMax[i], f[i]-end_i). Two meetings with the same end time overlap, so the binary search does not chain them.
The time complexity is O(nlog n) and the space complexity is O(n)$.
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 ansclass 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;
}
};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;
}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
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Include/Exclude | O(2^n) | O(n) | Small inputs or to verify correctness |
| Bottom-Up DP with Linear Scan | O(n^2) | O(n) | Deriving the recurrence when n is at most a few thousand |
| Sort + Binary Search + DP | O(n log n) | O(n) | General case and large inputs |
Frequently asked questions
Is Maximize Meeting Earnings with Idle Gaps easy or hard?
It is rated Hard on FleetCode. The difficulty comes from combining three techniques: sorting to define a valid order, DP to handle the choice of which meetings to take, and binary search to speed up predecessor lookup. Solving the recurrence correctly is the main hurdle.
Maximize Meeting Earnings with Idle Gaps Python or Java solution?
Sort the meetings by end time, precompute the end times as a separate list, and loop through meetings with a DP array. Python uses bisect_right for the binary search, and Java uses Arrays.binarySearch or a manual search on the sorted end times. Both run in O(n log n) time.
How to solve Maximize Meeting Earnings with Idle Gaps in O(n log n)?
Sort meetings by end time and build a DP array where dp[i] is the maximum earnings using the first i meetings. For each meeting, binary search the sorted end times to find the rightmost compatible predecessor j, then set dp[i] = max(dp[i-1], earnings[i] + dp[j]). The answer is dp[n].
What is the best approach for Maximize Meeting Earnings with Idle Gaps?
The best approach is to sort meetings by end time, then run a DP where each meeting either gets skipped or taken with its earnings added to the best compatible prefix. Use binary search to find the latest compatible meeting in O(log n) instead of scanning backward. The total time is O(n log n) with O(n) extra space.
What data structure is used in Maximize Meeting Earnings with Idle Gaps?
The solution uses a sorted array of meetings, a sorted array of end times for binary search, and a one-dimensional DP array. No hash map or tree structure is needed. The sorting and binary search do most of the work.
What is the time complexity of Maximize Meeting Earnings with Idle Gaps?
The optimal solution runs in O(n log n) time, dominated by sorting and the n binary searches. It uses O(n) extra space for the DP array and the sorted metadata. A naive recursive solution takes O(2^n) time, and a DP with linear scan takes O(n^2).
Is Maximize Meeting Earnings with Idle Gaps asked at Google, Amazon, or Meta?
This problem is tagged as Hard with a 39.0% acceptance rate on FleetCode. Company-specific frequency data is not listed for this problem, so check recent interview reports on your target company's question bank. Its patterns (sorting, binary search, DP) are common in interviews at large tech companies.