Welcome to Subscribe On Youtube

3893. Maximum Team Size with Overlapping Intervals 🔒

Description

You are given two integer arrays startTime and endTime of length n.

  • startTime[i] represents the start time of the ith employee.
  • endTime[i] represents the end time of the ith employee.

Two employees i and j can interact if their time intervals overlap. Two intervals are considered overlapping if they share at least one common time point.

A team is valid if there exists at least one employee in the team who can interact with every other member of the team.

Return an integer denoting the maximum possible size of such a team.

 

Example 1:

Input: startTime = [1,2,3], endTime = [4,5,6]

Output: 3

Explanation:

  • For i = 0 with interval [1, 4].
  • It overlaps with i = 1 having interval [2, 5] and i = 2 having interval [3, 6].
  • Thus, index 0 can interact with all other indices, so the team size is 3.

Example 2:

Input: startTime = [2,5,8], endTime = [3,7,9]

Output: 1

Explanation:

  • For i = 0, interval [2, 3] does not overlap with [5, 7] or [8, 9].
  • For i = 1, interval [5, 7] does not overlap with [2, 3] or [8, 9].
  • For i = 2, interval [8, 9] does not overlap with [2, 3] or [5, 7].
  • Thus, no index can interact with others, so the maximum team size is 1.

Example 3:

Input: startTime = [3,4,6], endTime = [8,5,7]

Output: 3

Explanation:

  • For i = 0 with interval [3, 8].
  • It overlaps with i = 1 having interval [4, 5] and i = 2 having interval [6, 7].
  • Thus, index 0 can interact with all other indices, so the team size is 3.

 

Constraints:

  • 1 <= n == startTime.length == endTime.length <= 105
  • 0 <= startTime[i] <= endTime[i] <= 109

Solutions

We first combine each employee’s start and end times into an interval array, $\textit{intervals}$, and sort all start times and end times separately.

For each employee $i$, we use binary search to compute how many employees have end times not earlier than employee $i$’s start time, and how many employees have start times not later than employee $i$’s end time. The difference between these two counts is the number of employees whose intervals overlap with employee $i$. We iterate through all employees, compute the overlap count for each one, and take the maximum as the answer.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$, where $n$ is the number of employees.

  • 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;
    }
};


  • 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


  • 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;
}

All Problems

All Solutions