3893. 最大重叠区间团队规模 🔒

题目描述

给定两个整数数组 startTime 和 endTime，长度为 n。

startTime[i] 表示第 i 个员工的开始时间。
endTime[i] 表示第 i 个员工的结束时间。

如果两个员工 i 和 j 的时间区间 有重叠，则他们可以进行互动。两个区间只要 至少有一个 公共时间点，就认为是重叠的。

如果一个团队中 至少存在一个 员工，可以与团队中的所有其他成员互动，则该团队是 有效的。

返回一个整数，表示这样的团队的 最大可能规模。

示例 1：

输入：startTime = [1,2,3], endTime = [4,5,6]

输出：3

解释：

对于 i = 0，区间为 [1, 4]。
它与 i = 1 的区间 [2, 5] 和 i = 2 的区间 [3, 6] 都有重叠。
因此，索引 0 可以与所有其他索引互动，团队规模为 3。

示例 2：

输入：startTime = [2,5,8], endTime = [3,7,9]

输出：1

解释：

对于 i = 0，区间 [2, 3] 与 [5, 7] 和 [8, 9] 都没有重叠。
对于 i = 1，区间 [5, 7] 与 [2, 3] 和 [8, 9] 都没有重叠。
对于 i = 2，区间 [8, 9] 与 [2, 3] 和 [5, 7] 都没有重叠。
因此，没有任何一个索引可以与其他所有人互动，最大团队规模为 1。

示例 3：

输入：startTime = [3,4,6], endTime = [8,5,7]

输出：3

解释：

对于 i = 0，区间为 [3, 8]。
它与 i = 1 的区间 [4, 5] 和 i = 2 的区间 [6, 7] 都有重叠。
因此，索引 0 可以与所有其他索引互动，团队规模为 3。

提示：

1 <= n == startTime.length == endTime.length <= 10⁵
0 <= startTime[i] <= endTime[i] <= 10⁹

解法

方法一：二分查找

我们首先将每个员工的开始时间和结束时间组合成一个区间 \(\textit{intervals}\)，并分别对所有员工的开始时间和结束时间进行排序。

对于每个员工 \(i\)，我们可以使用二分查找来计算出有多少员工的结束时间不早于 \(i\) 的开始时间，以及有多少员工的开始时间不晚于 \(i\) 的结束时间。两者的差值即为与员工 \(i\) 有重叠的员工数量。我们遍历所有员工，计算出与每个员工有重叠的员工数量，并取最大值即为答案。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是员工的数量。

Python3JavaC++GoTypeScript

class Solution:
    def maximumTeamSize(self, startTime: list[int], endTime: list[int]) -> int:
        intervals = list(zip(startTime, endTime))
        startTime.sort()
        endTime.sort()
        ans = 0
        for l, r in intervals:
            i = bisect_right(endTime, l - 1)
            j = bisect_right(startTime, r)
            ans = max(ans, j - i)
        return ans

class Solution {
    public int maximumTeamSize(int[] startTime, int[] endTime) {
        int n = startTime.length;
        int[][] intervals = new int[n][2];
        for (int i = 0; i < n; i++) {
            intervals[i][0] = startTime[i];
            intervals[i][1] = endTime[i];
        }
        Arrays.sort(startTime);
        Arrays.sort(endTime);

        int ans = 0;
        for (int[] it : intervals) {
            int l = it[0], r = it[1];

            int i = search(endTime, l - 1);
            int j = search(startTime, r);

            ans = Math.max(ans, j - i);
        }

        return ans;
    }

    private int search(int[] arr, int x) {
        int l = 0, r = arr.length;
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (arr[mid] > x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

class Solution {
public:
    int maximumTeamSize(vector<int>& startTime, vector<int>& endTime) {
        int n = startTime.size();
        vector<pair<int, int>> intervals(n);
        for (int i = 0; i < n; i++) {
            intervals[i] = {startTime[i], endTime[i]};
        }

        sort(startTime.begin(), startTime.end());
        sort(endTime.begin(), endTime.end());

        int ans = 0;
        for (const auto& [l, r] : intervals) {
            int i = upper_bound(endTime.begin(), endTime.end(), l - 1) - endTime.begin();
            int j = upper_bound(startTime.begin(), startTime.end(), r) - startTime.begin();
            ans = max(ans, j - i);
        }

        return ans;
    }
};

func maximumTeamSize(startTime []int, endTime []int) int {
    n := len(startTime)
    intervals := make([][2]int, n)
    for i := 0; i < n; i++ {
        intervals[i] = [2]int{startTime[i], endTime[i]}
    }

    sort.Ints(startTime)
    sort.Ints(endTime)

    ans := 0
    for _, it := range intervals {
        l, r := it[0], it[1]

        i := sort.Search(len(endTime), func(k int) bool { return endTime[k] > l-1 })
        j := sort.Search(len(startTime), func(k int) bool { return startTime[k] > r })

        ans = max(ans, j-i)
    }

    return ans
}

function maximumTeamSize(startTime: number[], endTime: number[]): number {
    const n = startTime.length;
    const intervals: [number, number][] = Array.from({ length: n }, (_, i) => [
        startTime[i],
        endTime[i],
    ]);

    startTime.sort((a, b) => a - b);
    endTime.sort((a, b) => a - b);

    let ans = 0;
    for (const [l, r] of intervals) {
        const i = search(endTime, l - 1);
        const j = search(startTime, r);

        ans = Math.max(ans, j - i);
    }

    return ans;
}

function search(arr: number[], x: number): number {
    let l = 0;
    let r = arr.length;
    while (l < r) {
        const mid = (l + r) >> 1;
        if (arr[mid] > x) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

3893. 最大重叠区间团队规模 🔒

题目描述

解法

方法一：二分查找

评论