Medium
题目描述
给定一个整数 eventTime，表示事件的持续时间。还给定两个长度为 n 的整数数组 startTime 和 endTime。
这些数组表示在事件期间（时间 t = 0 到 t = eventTime）发生的 n 个不重叠会议的开始和结束时间，其中第 i 个会议在时间 [startTime[i], endTime[i]] 期间举行。
你可以通过移动一个会议的开始时间来重新安排最多一个会议，同时保持相同的持续时间，使得会议保持不重叠，以最大化事件期间最长的连续空闲时间。
返回重新安排会议后可能的最大空闲时间。
注意，会议不能重新安排到事件时间之外，并且应保持不重叠。
注意：在此版本中，重新安排一个会议后，会议的相对顺序可以改变。
示例 1：
输入：eventTime = 5, startTime = [1,3], endTime = [2,5]
输出：2
解释：将会议 [1, 2] 重新安排到 [2, 3]，在时间 [0, 2] 期间没有会议。
示例 2：
输入：eventTime = 10, startTime = [0,7,9], endTime = [1,8,10]
输出：7
解释：将会议 [0, 1] 重新安排到 [8, 9]，在时间 [0, 7] 期间没有会议。
示例 3：
输入：eventTime = 10, startTime = [0,3,7,9], endTime = [1,4,8,10]
输出：6
解释：将会议 [3, 4] 重新安排到 [8, 9]，在时间 [1, 7] 期间没有会议。
示例 4：
输入：eventTime = 5, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]
输出：0
解释：事件期间没有时间不被会议占用。
约束条件：
1 <= eventTime <= 10^9n == startTime.length == endTime.length2 <= n <= 10^50 <= startTime[i] < endTime[i] <= eventTimeendTime[i] <= startTime[i + 1]，其中i在范围[0, n - 2]内。
解题思路
这是一道贪心算法题，需要通过重新安排一个会议来最大化连续空闲时间。
核心思路：
计算原始空闲时间段：首先找出所有现有的空闲时间段，包括事件开始前、会议间隔、事件结束后的空闲时间。
枚举移除会议：对于每个会议，假设将其移除，这会创造一个新的空闲时间段。然后尝试将这个会议重新安排到其他空闲时间段中。
合并空闲时间段：当移除一个会议后，可能会与相邻的空闲时间段合并，形成更大的连续空闲时间。
重新安排策略：将移除的会议尝试放入每个足够大的空闲时间段中，计算剩余的最大连续空闲时间。
算法步骤：
- 计算所有原始空闲时间段
- 对每个会议进行枚举：
- 移除该会议，合并相邻空闲时间段
- 尝试将该会议重新安排到其他空闲位置
- 计算重新安排后的最大连续空闲时间
- 返回所有可能情况中的最大值
这种方法的时间复杂度为 O(n²)，空间复杂度为 O(n)，适合题目的数据规模。
代码实现
class Solution {
public:
int maxFreeTime(int eventTime, vector<int>& startTime, vector<int>& endTime) {
int n = startTime.size();
// Calculate original gaps
vector<int> gaps;
if (startTime[0] > 0) gaps.push_back(startTime[0]);
for (int i = 1; i < n; i++) {
if (startTime[i] > endTime[i-1]) {
gaps.push_back(startTime[i] - endTime[i-1]);
}
}
if (endTime[n-1] < eventTime) gaps.push_back(eventTime - endTime[n-1]);
int maxFree = gaps.empty() ? 0 : *max_element(gaps.begin(), gaps.end());
// Try removing each meeting
for (int i = 0; i < n; i++) {
int duration = endTime[i] - startTime[i];
// Calculate gaps after removing meeting i
vector<int> newGaps;
// Gap before first meeting (if not removing first)
if (i > 0 && startTime[0] > 0) {
newGaps.push_back(startTime[0]);
} else if (i == 0 && n > 1 && startTime[1] > 0) {
newGaps.push_back(startTime[1]);
} else if (i == 0 && n == 1) {
newGaps.push_back(eventTime);
}
// Gaps between meetings
for (int j = 1; j < n; j++) {
if (j == i) continue;
int prevIdx = (j-1 == i) ? (j-2 >= 0 ? j-2 : -1) : j-1;
if (prevIdx >= 0 && prevIdx != i) {
if (startTime[j] > endTime[prevIdx]) {
newGaps.push_back(startTime[j] - endTime[prevIdx]);
}
} else if (prevIdx == -1) {
// j is the first remaining meeting
if (startTime[j] > 0) {
newGaps.push_back(startTime[j]);
}
}
}
// Handle the merged gap from removing meeting i
int leftBound = (i > 0) ? endTime[i-1] : 0;
int rightBound = (i < n-1) ? startTime[i+1] : eventTime;
if (rightBound > leftBound) {
newGaps.push_back(rightBound - leftBound);
}
// Gap after last meeting
int lastMeeting = -1;
for (int j = n-1; j >= 0; j--) {
if (j != i) {
lastMeeting = j;
break;
}
}
if (lastMeeting >= 0 && endTime[lastMeeting] < eventTime) {
// Check if we already added this gap
bool alreadyAdded = false;
if (lastMeeting == n-2 && i == n-1) alreadyAdded = true;
if (!alreadyAdded) {
newGaps.push_back(eventTime - endTime[lastMeeting]);
}
}
// Remove duplicates and sort
sort(newGaps.begin(), newGaps.end(), greater<int>());
// Try placing the removed meeting in each gap
for (int gap : newGaps) {
if (gap >= duration) {
vector<int> finalGaps = newGaps;
// Find and update the gap where we place the meeting
for (int& g : finalGaps) {
if (g == gap) {
g = gap - duration;
break;
}
}
sort(finalGaps.begin(), finalGaps.end(), greater<int>());
if (!finalGaps.empty()) {
maxFree = max(maxFree, finalGaps[0]);
}
break;
}
}
}
return maxFree;
}
};
class Solution:
def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int:
n = len(startTime)
# Calculate original gaps
gaps = []
if startTime[0] > 0:
gaps.append(startTime[0])
for i in range(1, n):
if startTime[i] > endTime[i-1]:
gaps.append(startTime[i] - endTime[i-1])
if endTime[n-1] < eventTime:
gaps.append(eventTime - endTime[n-1])
max_free = max(gaps) if gaps else 0
# Try removing each meeting
for i in range(n):
duration = endTime[i] - startTime[i]
# Calculate new gaps after removing meeting i
new_gaps = []
# Add gap at the beginning
if i == 0:
if n > 1:
new_gaps.append(startTime[1])
else:
new_gaps.append(eventTime)
else:
if startTime[0] > 0:
new_gaps.append(startTime[0])
# Add gaps between remaining meetings
prev_end = 0 if i == 0 else endTime[0]
for j in range(1 if i == 0 else 1, n):
if j == i:
continue
if j-1 == i:
if i > 0:
prev_end = endTime[i-1]
else:
prev_end = 0
else:
prev_end = endTime[j-1]
if startTime[j] > prev_end:
new_gaps.append(startTime[j] - prev_end)
prev_end = endTime[j]
# Handle the gap created by removing meeting i
left_bound = endTime[i-1] if i > 0 else 0
right_bound = startTime[i+1] if i < n-1 else eventTime
if right_bound > left_bound:
# Merge with existing gaps or create new one
merged = False
for k in range(len(new_gaps)):
# This is a simplified approach - we'll recalculate gaps properly
pass
new_gaps.append(right_bound - left_bound)
# Add gap at the end
last_meeting = -1
for j in range(n-1, -1, -1):
if j != i:
last_meeting = j
break
if last_meeting >= 0 and endTime[last_meeting] < eventTime:
new_gaps.append(eventTime - endTime[last_meeting])
# Remove duplicates and sort
new_gaps = sorted(set(new_gaps), reverse=True)
# Try placing the removed meeting in each gap
for gap in new_gaps:
if gap >= duration:
remaining_gaps = new_gaps.copy()
idx = remaining_gaps.index(gap)
remaining_gaps[idx] = gap - duration
remaining_gaps.sort(reverse=True)
if remaining_gaps:
max_free = max(max_free, remaining_gaps[0])
break
return max_free
public class Solution {
public int MaxFreeTime(int eventTime, int[] startTime, int[] endTime) {
int n = startTime.Length;
// Calculate original gaps
var gaps = new List<int>();
if (startTime[0] > 0) gaps.Add(startTime[0]);
for (int i = 1; i < n; i++) {
if (startTime[i] > endTime[i-1]) {
gaps.Add(startTime[i] - endTime[i-1]);
}
}
if (endTime[n-1] < eventTime) gaps.Add(eventTime - endTime[n-1]);
int maxFree = gaps.Count > 0 ? gaps.Max() : 0;
// Try removing each meeting
for (int i = 0; i < n; i++) {
int duration = endTime[i] - startTime[i];
// Calculate gaps after removing meeting i
var newGaps = new List<int>();
// Gap before first meeting
if (i > 0 && startTime[0] > 0) {
newGaps.Add(startTime[0]);
} else if (i == 0 && n > 1 && startTime[1] > 0) {
newGaps.Add(startTime[1]);
} else if (i == 0 && n == 1) {
newGaps.Add(eventTime);
}
// Gaps between meetings and handle merged gap
int leftBound = (i > 0) ? endTime[i-1] : 0;
int rightBound = (i < n-1) ? startTime[i+1] : eventTime;
if (rightBound > leftBound) {
newGaps.Add(rightBound - leftBound);
}
// Other gaps between remaining meetings
for (int j = 1; j < n; j++) {
if (j == i || j-1 == i) continue;
if (startTime[j] > endTime[j-1]) {
newGaps.Add(startTime[j] - endTime[j-1]);
}
}
// Gap after last meeting
int lastMeeting = -1;
for (int j = n-1; j >= 0; j--) {
if (j != i) {
lastMeeting = j;
break;
}
}
if (lastMeeting >= 0 && endTime[lastMeeting] < eventTime &&
(i != n-1 || lastMeeting != n-2)) {
newGaps.Add(eventTime - endTime[lastMeeting]);
}
newGaps.Sort((a, b) => b.CompareTo(a));
// Try placing the removed meeting in each gap
foreach (int gap in newGaps) {
if (gap >= duration) {
var finalGaps = new List<int>(newGaps);
int idx = finalGaps.IndexOf(gap);
finalGaps[idx] = gap - duration;
finalGaps.Sort((a, b) => b.CompareTo(a));
if (finalGaps.Count > 0) {
maxFree = Math.Max(maxFree, finalGaps[0]);
}
break;
}
}
}
return maxFree;
}
}
var maxFreeTime = function(eventTime, startTime, endTime) {
const n = startTime.length;
let maxFree = 0;
// Calculate current max free time without rescheduling
let currentMaxFree = Math.max(startTime[0], eventTime - endTime[n-1]);
for (let i = 0; i < n - 1; i++) {
currentMaxFree = Math.max(currentMaxFree, startTime[i+1] - endTime[i]);
}
maxFree = currentMaxFree;
// Try removing each meeting and find best placement
for (let i = 0; i < n; i++) {
const duration = endTime[i] - startTime[i];
// Create list of remaining meetings
const remaining = [];
for (let j = 0; j < n; j++) {
if (j !== i) {
remaining.push([startTime[j], endTime[j]]);
}
}
// Find all possible gaps where we can place the removed meeting
const gaps = [];
// Gap at the beginning
if (remaining.length === 0 || remaining[0][0] >= duration) {
gaps.push([0, remaining.length === 0 ? eventTime : remaining[0][0]]);
}
// Gaps between meetings
for (let j = 0; j < remaining.length - 1; j++) {
const gapStart = remaining[j][1];
const gapEnd = remaining[j+1][0];
if (gapEnd - gapStart >= duration) {
gaps.push([gapStart, gapEnd]);
}
}
// Gap at the end
if (remaining.length === 0 || eventTime - remaining[remaining.length-1][1] >= duration) {
gaps.push([remaining.length === 0 ? 0 : remaining[remaining.length-1][1], eventTime]);
}
// Try placing the meeting in each valid gap
for (const [gapStart, gapEnd] of gaps) {
// Try placing at the start of gap
if (gapStart + duration <= gapEnd) {
const newMeetings = [...remaining, [gapStart, gapStart + duration]];
newMeetings.sort((a, b) => a[0] - b[0]);
maxFree = Math.max(maxFree, getMaxFreeTime(newMeetings, eventTime));
}
// Try placing at the end of gap
if (gapEnd - duration >= gapStart) {
const newMeetings = [...remaining, [gapEnd - duration, gapEnd]];
newMeetings.sort((a, b) => a[0] - b[0]);
maxFree = Math.max(maxFree, getMaxFreeTime(newMeetings, eventTime));
}
}
}
return maxFree;
};
function getMaxFreeTime(meetings, eventTime) {
if (meetings.length === 0) return eventTime;
let maxFree = Math.max(meetings[0][0], eventTime - meetings[meetings.length-1][1]);
for (let i = 0; i < meetings.length - 1; i++) {
maxFree = Math.max(maxFree, meetings[i+1][0] - meetings[i][1]);
}
return maxFree;
}
复杂度分析
| 复杂度 | 大小 |
|---|---|
| 时间复杂度 | O(n²) |
| 空间复杂度 | O(n) |
其中 n 是会议的数量。时间复杂度为 O(n²) 是因为需要枚举每个会议进行移除，每次移除后需要重新计算空闲时间段。空间复杂度为 O(n) 用于存储空闲时间段。