跳转至

3440. 重新安排会议得到最多空余时间 II

题目描述

给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。

同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 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 <= 109
  • n == startTime.length == endTime.length
  • 2 <= n <= 105
  • 0 <= startTime[i] < endTime[i] <= eventTime
  • endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。

解法

方法一：贪心

根据题目描述，对于会议 \(i\)，我们记它左侧非空闲位置为 \(l_i\)，右侧非空闲位置为 \(r_i\)，记会议 \(i\) 的时长为 \(w_i = \text{endTime}[i] - \text{startTime}[i]\)，则：

\[ l_i = \begin{cases} 0 & i = 0 \\\\ \text{endTime}[i - 1] & i \gt 0 \end{cases} \]
\[ r_i = \begin{cases} \text{eventTime} & i = n - 1 \\\\ \text{startTime}[i + 1] & i \lt n - 1 \end{cases} \]

那么它可以向左移动，也可以向右移动，此时空闲时间为：

\[ r_i - l_i - w_i \]

如果左侧存在最大的空闲时间 \(\text{pre}_{i - 1}\)，满足 \(\text{pre}_{i - 1} \geq w_i\)，则可以将会议 \(i\) 向左移动到该位置，得到新的空闲时间：

\[ r_i - l_i \]

同理，如果右侧存在最大的空闲时间 \(\text{suf}_{i + 1}\)，满足 \(\text{suf}_{i + 1} \geq w_i\)，则可以将会议 \(i\) 向右移动到该位置，得到新的空闲时间：

\[ r_i - l_i \]

因此，我们首先预处理两个数组 \(\text{pre}\) 和 \(\text{suf}\)，其中 \(\text{pre}[i]\) 表示 \([0, i]\) 范围内的最大空闲时间，\(\text{suf}[i]\) 表示 \([i, n - 1]\) 范围内的最大空闲时间。然后遍历每个会议 \(i\)，计算它移动后的最大空闲时间，取最大值即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为会议的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxFreeTime(
        self, eventTime: int, startTime: List[int], endTime: List[int]
    ) -> int:
        n = len(startTime)
        pre = [0] * n
        suf = [0] * n
        pre[0] = startTime[0]
        suf[n - 1] = eventTime - endTime[-1]
        for i in range(1, n):
            pre[i] = max(pre[i - 1], startTime[i] - endTime[i - 1])
        for i in range(n - 2, -1, -1):
            suf[i] = max(suf[i + 1], startTime[i + 1] - endTime[i])
        ans = 0
        for i in range(n):
            l = 0 if i == 0 else endTime[i - 1]
            r = eventTime if i == n - 1 else startTime[i + 1]
            w = endTime[i] - startTime[i]
            ans = max(ans, r - l - w)
            if i and pre[i - 1] >= w:
                ans = max(ans, r - l)
            elif i + 1 < n and suf[i + 1] >= w:
                ans = max(ans, r - l)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {
        int n = startTime.length;
        int[] pre = new int[n];
        int[] suf = new int[n];

        pre[0] = startTime[0];
        suf[n - 1] = eventTime - endTime[n - 1];

        for (int i = 1; i < n; i++) {
            pre[i] = Math.max(pre[i - 1], startTime[i] - endTime[i - 1]);
        }

        for (int i = n - 2; i >= 0; i--) {
            suf[i] = Math.max(suf[i + 1], startTime[i + 1] - endTime[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int l = (i == 0) ? 0 : endTime[i - 1];
            int r = (i == n - 1) ? eventTime : startTime[i + 1];
            int w = endTime[i] - startTime[i];
            ans = Math.max(ans, r - l - w);

            if (i > 0 && pre[i - 1] >= w) {
                ans = Math.max(ans, r - l);
            } else if (i + 1 < n && suf[i + 1] >= w) {
                ans = Math.max(ans, r - l);
            }
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int maxFreeTime(int eventTime, vector<int>& startTime, vector<int>& endTime) {
        int n = startTime.size();
        vector<int> pre(n), suf(n);

        pre[0] = startTime[0];
        suf[n - 1] = eventTime - endTime[n - 1];

        for (int i = 1; i < n; ++i) {
            pre[i] = max(pre[i - 1], startTime[i] - endTime[i - 1]);
        }

        for (int i = n - 2; i >= 0; --i) {
            suf[i] = max(suf[i + 1], startTime[i + 1] - endTime[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int l = (i == 0) ? 0 : endTime[i - 1];
            int r = (i == n - 1) ? eventTime : startTime[i + 1];
            int w = endTime[i] - startTime[i];
            ans = max(ans, r - l - w);

            if (i > 0 && pre[i - 1] >= w) {
                ans = max(ans, r - l);
            } else if (i + 1 < n && suf[i + 1] >= w) {
                ans = max(ans, r - l);
            }
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func maxFreeTime(eventTime int, startTime []int, endTime []int) int {
    n := len(startTime)
    pre := make([]int, n)
    suf := make([]int, n)

    pre[0] = startTime[0]
    suf[n-1] = eventTime - endTime[n-1]

    for i := 1; i < n; i++ {
        pre[i] = max(pre[i-1], startTime[i]-endTime[i-1])
    }

    for i := n - 2; i >= 0; i-- {
        suf[i] = max(suf[i+1], startTime[i+1]-endTime[i])
    }

    ans := 0
    for i := 0; i < n; i++ {
        l := 0
        if i > 0 {
            l = endTime[i-1]
        }
        r := eventTime
        if i < n-1 {
            r = startTime[i+1]
        }
        w := endTime[i] - startTime[i]
        ans = max(ans, r-l-w)

        if i > 0 && pre[i-1] >= w {
            ans = max(ans, r-l)
        } else if i+1 < n && suf[i+1] >= w {
            ans = max(ans, r-l)
        }
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function maxFreeTime(eventTime: number, startTime: number[], endTime: number[]): number {
    const n = startTime.length;
    const pre: number[] = Array(n).fill(0);
    const suf: number[] = Array(n).fill(0);

    pre[0] = startTime[0];
    suf[n - 1] = eventTime - endTime[n - 1];

    for (let i = 1; i < n; i++) {
        pre[i] = Math.max(pre[i - 1], startTime[i] - endTime[i - 1]);
    }

    for (let i = n - 2; i >= 0; i--) {
        suf[i] = Math.max(suf[i + 1], startTime[i + 1] - endTime[i]);
    }

    let ans = 0;
    for (let i = 0; i < n; i++) {
        const l = i === 0 ? 0 : endTime[i - 1];
        const r = i === n - 1 ? eventTime : startTime[i + 1];
        const w = endTime[i] - startTime[i];

        ans = Math.max(ans, r - l - w);

        if (i > 0 && pre[i - 1] >= w) {
            ans = Math.max(ans, r - l);
        } else if (i + 1 < n && suf[i + 1] >= w) {
            ans = Math.max(ans, r - l);
        }
    }

    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
impl Solution {
    pub fn max_free_time(event_time: i32, start_time: Vec<i32>, end_time: Vec<i32>) -> i32 {
        let n = start_time.len();
        let mut pre = vec![0; n];
        let mut suf = vec![0; n];

        pre[0] = start_time[0];
        suf[n - 1] = event_time - end_time[n - 1];

        for i in 1..n {
            pre[i] = pre[i - 1].max(start_time[i] - end_time[i - 1]);
        }

        for i in (0..n - 1).rev() {
            suf[i] = suf[i + 1].max(start_time[i + 1] - end_time[i]);
        }

        let mut ans = 0;
        for i in 0..n {
            let l = if i == 0 { 0 } else { end_time[i - 1] };
            let r = if i == n - 1 { event_time } else { start_time[i + 1] };
            let w = end_time[i] - start_time[i];
            ans = ans.max(r - l - w);

            if i > 0 && pre[i - 1] >= w {
                ans = ans.max(r - l);
            } else if i + 1 < n && suf[i + 1] >= w {
                ans = ans.max(r - l);
            }
        }

        ans
    }
}

评论