본문으로 건너뛰기

3440 - Reschedule Meetings for Maximum Free Time II

정보

풀이 키워드​

스포주의

그리디


풀이 코드​

정보
  • 메모리: 59700 KB
  • 시간: 3 ms
class Solution {
    public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {
        int n = startTime.length;

        // n+1 gaps exist for n meetings
        int[] gaps = new int[n+1];
        gaps[0] = startTime[0];
        gaps[n] = eventTime - endTime[n-1];
        for (int i = 1; i < n; ++i) {
            gaps[i] = startTime[i] - endTime[i-1];
        }

        // pre-calc max right gap
        int[] rmax = new int[n+1];
        for (int i = n-1; -1 < i; --i) {
            rmax[i] = Math.max(rmax[i+1], gaps[i+1]);
        }

        // think event[i-1] as the i-th event
        int lmax = 0;
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int len = endTime[i-1] - startTime[i-1];

            if (lmax >= len || rmax[i] >= len) // moveable
                ans = Math.max(ans, gaps[i-1]+len+gaps[i]);

            ans = Math.max(ans, gaps[i-1]+gaps[i]); // not moveable
            lmax = lmax < gaps[i-1] ? gaps[i-1] : lmax;
        }

        return ans;
    }
}

풀이 해설​

어느 특정 미팅을 기준으로 잡고, 그 미팅의 좌/우 여백들 중에 미팅을 끼워넣을 수 있는지의 여부를 판단한 후
(단, 인접 여백 제외)

가능하면 lmax + 미팅길이 + rmax, 불가능하면 lmax + rmax로 최대값을 갱신해나가면 된다.

나머진 WIP


메모​

  • 부분합 유형은 아니지만 부분합 방식의 사고를 해야 함. 배열 precalc...
  • 그림 안그리고 풀면 은근 인덱스 값 헷갈림