In this scheduling optimization problem, we're given a series of non-overlapping meetings and a total event duration. The challenge is to reschedule up to k meetings to maximize the longest continuous free time within the event window.
📌 Problem Summary
You are given:
-
eventTime: Total event duration -
startTime,endTime: Arrays representing non-overlapping meetings -
k: Maximum number of meetings you can reschedule
Each meeting must retain its duration and order. You may shift up to k meetings to maximize the longest continuous free time within the event window [0, eventTime].
💡 Intuition
- Between every two meetings, there's a gap.
-
Gaps include:
- Before the first meeting
- Between meetings
- After the last meeting
Rescheduling meetings can shift these gaps, helping us merge multiple small gaps into a larger one.
To solve this, we:
- Calculate all gaps
- Slide a window of size
k+1over the gaps - Keep track of the maximum sum of
k+1consecutive gaps
🧰 C++ Code
class Solution {
public:
int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
const vector<int> gaps = getGaps(eventTime, startTime, endTime);
int windowSum = accumulate(gaps.begin(), gaps.begin() + k + 1, 0);
int ans = windowSum;
for (int i = k + 1; i < gaps.size(); ++i) {
windowSum += gaps[i] - gaps[i - k - 1];
ans = max(ans, windowSum);
}
return ans;
}
private:
vector<int> getGaps(int eventTime, const vector<int>& startTime, const vector<int>& endTime) {
vector<int> gaps{startTime[0]};
for (int i = 1; i < startTime.size(); ++i)
gaps.push_back(startTime[i] - endTime[i - 1]);
gaps.push_back(eventTime - endTime.back());
return gaps;
}
};
🐍 Python Code
def maxFreeTime(eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:
def getGaps():
gaps = [startTime[0]]
for i in range(1, len(startTime)):
gaps.append(startTime[i] - endTime[i - 1])
gaps.append(eventTime - endTime[-1])
return gaps
gaps = getGaps()
window_sum = sum(gaps[:k+1])
result = window_sum
for i in range(k+1, len(gaps)):
window_sum += gaps[i] - gaps[i - k - 1]
result = max(result, window_sum)
return result
💻 JavaScript Code
var maxFreeTime = function(eventTime, k, startTime, endTime) {
const getGaps = () => {
const gaps = [startTime[0]];
for (let i = 1; i < startTime.length; i++) {
gaps.push(startTime[i] - endTime[i - 1]);
}
gaps.push(eventTime - endTime[endTime.length - 1]);
return gaps;
};
const gaps = getGaps();
let windowSum = gaps.slice(0, k + 1).reduce((a, b) => a + b, 0);
let result = windowSum;
for (let i = k + 1; i < gaps.length; i++) {
windowSum += gaps[i] - gaps[i - k - 1];
result = Math.max(result, windowSum);
}
return result;
};
📝 Key Notes
- Time Complexity: O(n)
- Space Complexity: O(n)
- This problem reduces to a sliding window max sum over the
gapsarray.
✅ Final Thoughts
A clever use of gaps and a sliding window technique makes this problem tractable even at scale. Always reduce the problem to simple parts — here, it’s just about gaps and how to shift them optimally. ✅
Top comments (2)
Good One.
Thanks Anna