3439. Reschedule Meetings for Maximum Free Time I

문제

You are given an integer eventTime denoting the duration of an event, where the event occurs from time t = 0 to time t = eventTime.

You are also given two integer arrays startTime and endTime, each of length n. These represent the start and end time of n non-overlapping meetings, where the ith meeting occurs during the time [startTime[i], endTime[i]].

You can reschedule at most k meetings by moving their start time while maintaining the same duration, to maximize the longest continuous period of free time during the event.

The relative order of all the meetings should stay the same and they should remain non-overlapping.

Return the maximum amount of free time possible after rearranging the meetings.

Note that the meetings can not be rescheduled to a time outside the event.

0 ~ eventTime 까지의 타임 테이블이 있습니다.
startTime과 endTime은 절대 겹치지 않는 i번째 이벤트의 시작시간과 끝 시간이 적혀 있습니다.
사용자는 k번에 한해 이벤트의 길이를 유지하면서 시작시간을 변경할수 있는데,
다만 이동할 때에는 이벤트간 상대적인 위치를 유지해야 합니다.
이벤트가 없는 시간을 가장 길게 만들때, 그 길이를 구하시오

예시

Input: eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5]

Output: 2

1-2 이벤트를 2-3으로 옮기면 0-2 만큼의 빈 시간이 생긴다

제한

• $1 <= eventTime <= 10^9$
• $n == startTime.length == endTime.length$
• $2 <= n <= 10^5$
• $1 <= k <= n$
• $0 <= startTime[i] < endTime[i] <= eventTime$
• endTime[i] <= startTime[i + 1] where i lies in the range [0, n - 2]

풀이

• 가장 중요한 점은 우리가 필요한것은 하나의 가장 긴 시간이라는 것이다
• 일단 먼저 주어진 값들을 통해 빈 시간들의 배열을 찾아 준 다음에
• k번 이동했을때 만들수 있는 가장 긴 빈 시간을 찾는데
• 이것은 곧 k + 1 사이즈의 빈 시간 배열의 window의 값의 합과 같다는것이다
  • 멀리 떨어진 시간들을 합쳐봤자 하나의 긴 빈 시간을 만들수 없기 때문에

class Solution:
    def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:
        last_end = 0
        time = []

        for s, e in zip(startTime, endTime):
            time.append(s - last_end)
            last_end = e

        if eventTime > last_end:
            time.append(eventTime - last_end)

        ans = window = sum(time[:min(k + 1, len(time))])

        for i in range(k + 1, len(time)):
            window += time[i] - time[i - k - 1]
            ans = max(ans, window)

        return ans