3440. Reschedule Meetings for Maximum Free Time II

23 February 2025
[ algorithms , leetcode , medium-hard ]

Give this problem a try 3440. Reschedule Meetings for Maximum Free Time II.

Problem Statement

You are given an integer eventTime denoting the duration of an event. You are also given two integer arrays startTime and endTime, each of length n.

These represent the start and end times of n non-overlapping meetings that occur during the event between time t = 0 and time t = eventTime, where the ith meeting occurs during the time [startTime[i], endTime[i]].

You can reschedule at most one meeting by moving its start time while maintaining the same duration, such that the meetings remain non-overlapping, to maximize the longest continuous period of free time during the event.

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 and they should remain non-overlapping.

Note: In this version, it is valid for the relative ordering of the meetings to change after rescheduling one meeting.

Example 1:

Input: eventTime = 5, startTime = [1,3], endTime = [2,5]
Output: 2
Explanation: Reschedule the meeting at [1, 2] to [2, 3], leaving no meetings during the time [0, 2].

Example 2:

Input: eventTime = 10, startTime = [0,7,9], endTime = [1,8,10]
Output: 7
Explanation: Reschedule the meeting at [0, 1] to [8, 9], leaving no meetings during the time [0, 7].

Example 3:

Input: eventTime = 10, startTime = [0,3,7,9], endTime = [1,4,8,10]
Output: 6
Explanation: Reschedule the meeting at [3, 4] to [8, 9], leaving no meetings during the time [1, 7].

Example 4:

Input: eventTime = 5, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]
Output: 0
Explanation: There is no time during the event not occupied by meetings.

Constraints

1 <= eventTime <= 1e9
n == startTime.length == endTime.length
2 <= n <= 1e5
0 <= startTime[i] < endTime[i] <= eventTime
endTime[i] <= startTime[i + 1] where i lies in the range [0, n - 2].

Prerequisite Knowledge

Prefix / Suffix Max

Example Code

class Solution {
    public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {
        int n = startTime.length;

        int[][] events = new int[n][2];
        for (int i = 0; i < n; i++) events[i] = new int[] {startTime[i], endTime[i]};

        int[] spaces = new int[n+1];
        spaces[0] = events[0][0] - 0;
        for (int i = 1; i < n; i++) {
            spaces[i] = events[i][0] - events[i-1][1];
        }
        spaces[n] = eventTime - events[n-1][1];

        int maxSpace = 0;
        for (int i = 0; i < n+1; i++) maxSpace = Math.max(maxSpace, spaces[i]);

        // maxPref = max prefix previous space 0 -> i
        // maxSuff = max suffix previous space i -> n-1

        // check maxPref[i-2] and maxSuff[i+2]
        int[] maxPref = new int[n];
        int[] maxSuff = new int[n];

        // maxPref[i] = prefix max spaces 0 -> i event
        maxPref[0] = spaces[0];
        for (int i = 1; i < n; i++) maxPref[i] = Math.max(maxPref[i-1], spaces[i]);

        // maxSuff[i] = suffic max spaces i -> n-1 event
        maxSuff[n-1] = spaces[n];
        for (int i = n-2; i >= 0; i--) maxSuff[i] = Math.max(maxSuff[i+1], spaces[i+1]);

        int answer = maxSpace;

        for (int i = 0; i < n; i++) {
            int prev = spaces[i];
            int next = spaces[i+1];
            int eventSpace = events[i][1] - events[i][0];

            // consider 0 and n-1 independently
            // event[0] can only be moved to maxSuff[1]
            // event[n-1] can only be moved to maxPref[n-2]

            if (i == 0) {
                int maxSuffSpace = maxSuff[1];
                if (eventSpace > maxSuffSpace) {
                    answer = Math.max(answer, prev + next);
                }
                else {
                    answer = Math.max(answer, prev + next + eventSpace);
                }
                continue;
            }

            if (i == n-1) {
                int maxPrefSpace = maxPref[n-2];
                if (eventSpace > maxPrefSpace) {
                    answer = Math.max(answer, prev + next);
                }
                else {
                    answer = Math.max(answer, prev + next + eventSpace);
                }
                continue;
            }

            // consider maxPref[i-1] and maxSuff[i+1]
            int maxPrefSpace = maxPref[i-1];
            int maxSuffSpace = maxSuff[i+1];

            if (eventSpace > maxPrefSpace && eventSpace > maxSuffSpace) {
                // can only slide within bound
                answer = Math.max(answer, prev + next);
            }
            else {
                // can allocate eventSpace to some other space
                answer = Math.max(answer, prev + next + eventSpace);
            }
        }

        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

(Special) Explanation

Sign-off

Congratulations on making it this far! Although LeetCode rates this as a medium question, I actually consider it medium-hard because it requires a smart mix of basic techniques and sharp observation to reduce to O(N) complexity. Best of luck in your future competitions!