Reschedule Meetings for Maximum Free Time II

This problem is basically yesterday's problem except you can:

• reschedule maximum only 1 meeting
• relative orderings of meetings can change.

This basically means we are concatenating adjacent break values (where break[i] is the positive time difference between endTime[i] and startTime[i+1]) and trying to find the maximum possible sum.

However, what sets this apart from yesterday's question, is that we have to check if there exists another break value (outside of the 2 that we are concatenating) GREATER than our current meeting (which is simply the positive time difference between startTime[i] and endTime[i]) which we can move our current meeting to.

For example, let the ~ denote a meeting.

 | ~ |   |   |*~*|   |   |   | ~ |   | ~ |
 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10|

In our case, to find the maximum contiguous period of free time, we can simply shift the meeting from 3 to 4 to 8 to 9 as it is a break value that is not the 2 that we are concatenating, giving us a max free time of 6.

 | ~ |   |   |   |   |   |   | ~ |*~*| ~ |
 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10|

The easiest way we can check this, is for every meeting, we find the maximum break value to the left and to the right of the current meeting (using some sort of prefix sum array), and see if there exists a break value that can house our current meeting. Then, we have 2 cases:

• if it can, then we can concatenate adjacent break values and add the current meeting duration to the sum
  • this is because, we are effectively moving the meeting into Narnia; never to be seen ever again
• if it cannot, then we only concatenate adjacent break values

Finally, we just keep track of the max value and return it.

However, this solution is in O(n) space complexity, but it is possible to implement it in O(1) instead.

Effectively, what my algorithm is doing is iterating both from left to right and right to left. While it is iterating

• from left to right, it calculates the maximum break value on the left at each index.
• from right to left, it calculates the maximum break value on the right at each index.

This means that at every index, eventually, an if statement will run checking whether there is a break value large enough to fit itself on both the left and right side of the current meeting interval. In the code example below, I have

• variable i that iterates from 0 to n-1
• variable j that iterates from n-1 to 0

and also annoted the sections which contain the logic checking if there exists an interval largen enough to house the current meeting time.

code

class Solution {
public:
    int maxFreeTime(int eventTime, vector<int>& startTime, vector<int>& endTime) {
        int n = startTime.size();
        int ans = 0;
        int maxLHSInterval = 0;
        int maxRHSInterval = 0;
        for (int i = 0; i < n; ++i) {
            // from left to right
            int LHSLeftIndex = (i == 0) ? 0 : endTime[i-1];
            int LHSRightIndex = (i == n-1) ? eventTime : startTime[i+1];

            int LHSCurrentInterval = endTime[i] - startTime[i];

            // at index `i`, it checks if there exists an interval LARGE ENOUGH to house itself on the LEFT
            if (maxLHSInterval >= LHSCurrentInterval) {
                ans = max(ans, LHSRightIndex - LHSLeftIndex);
            }

            maxLHSInterval = max(maxLHSInterval, startTime[i] - ((i == 0) ? 0 : endTime[i-1]));
            ans = max(ans, LHSRightIndex - LHSLeftIndex - LHSCurrentInterval);

            // from right to left
            int j = n-i-1;
            int RHSLeftIndex = (j == 0) ? 0 : endTime[j-1];
            int RHSRightIndex = (j == n-1) ? eventTime : startTime[j+1];

            int RHSCurrentInterval = endTime[j] - startTime[j];

            // at index `j`, it checks if there exists an interval LARGE ENOUGH to house itself on the RIGHT
            if (maxRHSInterval >= RHSCurrentInterval) {
                ans = max(ans, RHSRightIndex - RHSLeftIndex);
            }
            maxRHSInterval = max(maxRHSInterval, ((j == n-1) ? eventTime : startTime[j+1]) - endTime[j]);
        }
        return ans;
    }
};

complexity

• Time: O(n)
• Space: O(1)

time taken

• 21 minutes and 36 seconds