Find employees with overlapping wortktime hours

Question

Given StartTime and endTime for N employees, an employee can form a team if his working hour overlaps with other employees' (both startTime and endTime inclusive).
Find the maximum team size.
Example:
startTime = [2,5,6,8]
endTime = [5,6,10,9]: answer is 3.
emp1 works from 2-5
emp2 works from 5-6
emp3 works from 6-10
emp4 works from 8-9

- emp1 can overlap only with emp2 at 5th hour, so max team size for emp1 is 2
- emp2 can overlap at 5th hour with emp1 and 6th hour with emp3, so max team size is 3
- emp3 also 3
- emp4 - 2
So answer is 3.

I have a working solution, but it is not optimized and all test cases are not passing (not failing but timeout).
Whatever solution you try to bring, verify that output is 3 for above test case.

startTime = [2,5,6,8]
endTime = [5,6,10,9]
n = len(startTime)
max_time = 0
for i in range(n):
    temp = 0
    for j in range(n):
        if i == j:
            continue
        if ((startTime[i] <= startTime[j] <= endTime[i]) or (startTime[i] <= endTime[j] <= endTime[i])):
            temp+=1
    max_time = max(max_time, temp)
print(max_time+1)

Answer 1

Sort the intervals by start time. Then, we will make two passes over the list, once in each direction.

During the forward pass, we use a binary indexed tree to maintain the end times (after coordinate compression) of previous intervals and for each interval, the number of intervals on its left that overlap with it is equal to the number of previous end times that are greater than or equal to its start time.

The backward pass is similar, except we now maintain the start times of previous intervals and query for start times that are less than or equal to the current interval's end time to get the number of intervals on its right that overlap with it.

Finally, the answer is the one more than the maximum number of total overlaps with any specific interval.

The time complexity is O(N log N).

from bisect import bisect_left
import itertools

def solve(start_times: list[int], end_times: list[int]):
    sorted_times = sorted(start_times + end_times)
    bit = [0] * len(sorted_times)
    def update(i, v):
        while i < len(bit):
            bit[i] += v
            i |= i + 1
    def query(i):
        res = 0
        while i >= 0:
            res += bit[i]
            i = (i & (i + 1)) - 1
        return res
    indexes = sorted(range(len(end_times)), key=lambda i: start_times[i])
    left_overlaps = [0] * len(end_times)
    for _, group in itertools.groupby(indexes, key=lambda i: start_times[i]):
        group = list(group)
        for i in group:
            left_overlaps[i] = query(len(bit) - 1) - query(bisect_left(sorted_times, start_times[i]) - 1)
        for i in group:
            update(bisect_left(sorted_times, end_times[i]), 1)
    bit = [0] * len(bit)
    ans = 0
    for _, group in itertools.groupby(reversed(indexes), key=lambda i: start_times[i]):
        group = list(group)
        for i in group:
            update(bisect_left(sorted_times, start_times[i]), 1)
        for i in group:
            ans = max(ans, left_overlaps[i] + query(bisect_left(sorted_times, end_times[i])))
    return ans

Answer 2

Vanilla python solution might look like this:

startTime = [2,5,6,8]
endTime = [5,6,10,9]

times = list(zip(startTime, endTime))
res = []
for i in times:
    t = []
    for j in times:
        t.append(max(i[0], j[0]) <= min(i[1], j[1]))
    res.append(sum(t))
    
print(max(res))

3

pandas allows to do it this way:

import pandas as pd

df = pd.DataFrame()
df['intervals'] = pd.IntervalIndex.from_arrays(startTime,
                                               endTime,
                                               closed='both')
ans = int(df.apply(lambda x: pd.IntervalIndex(df["intervals"]).overlaps(x["intervals"]).sum(), axis=1).max())
print(ans)