[LeetCode] 3439. Reschedule Meetings for Maximum Free Time I

[문제 링크]

https://leetcode.com/problems/reschedule-meetings-for-maximum-free-time-i/description/

 

[문제]

목표는 여러 회의들의 일정을 조정하여 가능한 한 최대의 여유 시간을 확보하는 것입니다. 주어진 회의들 사이에 연속된 여유 시간을 찾고, 그 여유 시간 중에서 k개의 회의를 이동시켜 여유 시간을 최대화하는 방법을 찾는 문제입니다.

eventTime: 이벤트가 끝나는 시간 (예: 하루의 끝) k: 회의를 이동시킬 수 있는 최대 횟수 (즉, k개의 회의를 이동할 수 있음) startTime: 각 회의의 시작 시간 배열 endTime: 각 회의의 종료 시간 배열

여기서 각 회의의 시작 시간과 종료 시간은 겹치지 않으며, k개의 회의를 이동시키는 것으로 가능한 최대의 연속적인 여유 시간을 구하는 것이 목표입니다.

[풀이 과정]

누적합과 슬라이딩 윈도우를 확실하게 알아야 풀 수 있는 문제였습니다.

문제의 핵심은 회의 사이의 시간을 구하고 회의 2개를 옮길 수 있다면

3개의 쉬는 시간을 합쳐 가장 높은 시간이 나오는 걸 반환하면 됩니다.

 

[코드]

class Solution {
    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int n = startTime.length;
        // 첫 회의 전 남는 시간, 마지막 회의 후 남는 시간도 구해야하기 때문
        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];
        }

        // 누적합 (누적합으로 결과를 구해야 중복계산 x)
        // pref[0] = 0
        int[] pref = new int[n + 2];

        for(int i = 1; i < n + 2; i ++) {
            pref[i] = pref[i - 1] + gaps[i - 1];
        }

        int answer = 0; 

        // 슬라이딩 윈도우
        // 구간을 한칸씩 밀면서 빠져나가는 값을 제외하는 로직
        for(int i = k + 1; i < n+2; i++) {
            answer = Math.max(answer, pref[i] - pref[i - (k+1)]);
        }

        return answer;
    }
}

[회고]

진짜 너무 어려웠다. 누적합과 슬라이딩 윈도우를 합쳐서 응용하는 문제였는데

이해하는대도 오래걸리고 머리아팠습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.