Scale Engineer

Reschedule Meetings for Maximum Free Time I

Med
#3056Time: O(N^2). The main loop iterates `N+1` times. Inside this loop, calculating costs and durations for prefixes and suffixes involves nested loops that take O(N) time in total. This results in a quadratic time complexity.Space: O(N) to store the durations of the meetings. This can be optimized to O(1) if durations are calculated on the fly.
Patterns
Sliding WindowGreedy
Data structures
Array

Prompt

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.

 

Example 1:

Input: eventTime = 5, k = 1, 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, k = 1, startTime = [0,2,9], endTime = [1,4,10]

Output: 6

Explanation:

Reschedule the meeting at [2, 4] to [1, 3], leaving no meetings during the time [3, 9].

Example 3:

Input: eventTime = 5, k = 2, 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 <= 109
  • n == startTime.length == endTime.length
  • 2 <= n <= 105
  • 1 <= k <= n
  • 0 <= startTime[i] < endTime[i] <= eventTime
  • endTime[i] <= startTime[i + 1] where i lies in the range [0, n - 2].

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically checks every possible way to create a large free time gap. It considers the initial gaps between meetings and then, for each potential gap, calculates the maximum size it can be expanded to by rescheduling meetings on one or both sides, staying within the k move limit. This is done without any precomputation, leading to repeated calculations.

Algorithm

  1. Initialize max_free_time with the largest initial gap (at the start, end, or between any two meetings).
  2. Pre-calculate the duration of each meeting.
  3. Iterate through each possible split point i from 1 to n (for a gap after meeting i-1).
  4. For each i, calculate the cost and duration of packing the prefix meetings 0..i-1 by iterating from j=0 to i-1.
  5. If the prefix packing cost is ≤ k, calculate the new gap startTime[i] - (packed_prefix_duration) and update max_free_time.
  6. Similarly, for each split point i from 0 to n-1 (for a gap before meeting i), calculate the cost and duration of packing the suffix meetings i..n-1.
  7. If the suffix packing cost is ≤ k, calculate the new gap (eventTime - packed_suffix_duration) - endTime[i-1] and update max_free_time.
  8. For each split point i from 0 to n, calculate the combined cost of packing both the prefix 0..i-1 and suffix i..n-1.
  9. If the combined cost is ≤ k, calculate the gap eventTime - total_duration and update max_free_time.
  10. Return the final max_free_time.

Walkthrough

The algorithm first considers all initial free time intervals: startTime[0] (gap at the start), eventTime - endTime[n-1] (gap at the end), and startTime[i] - endTime[i-1] for 1 <= i < n. The maximum of these is our baseline answer.

Then, for each potential gap (including those at the ends), we explore three possibilities of using our k moves:

  1. Pack the prefix: For a gap between meetings i-1 and i, we can try to pack all meetings 0..i-1 to start at time 0. We calculate the cost (number of moves) for this by iterating through these meetings. If cost <= k, we calculate the new, larger gap: startTime[i] - (end time of packed prefix).

  2. Pack the suffix: Similarly, we can try to pack all meetings i..n-1 to end at eventTime. We calculate the cost and, if affordable, the new gap: (start time of packed suffix) - endTime[i-1].

  3. Pack both prefix and suffix: We can try to pack both the prefix and suffix parts. We calculate the combined cost. If cost <= k, the new gap is (start time of packed suffix) - (end time of packed prefix), which simplifies to eventTime - total_duration.

For each split point i, these calculations (costs and durations) are done by iterating through the relevant meetings. The overall maximum free time found across all these scenarios and all split points is the result.

class Solution {    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {        int n = startTime.length;        if (n == 0) return eventTime;         long[] durations = new long[n];        for (int i = 0; i < n; i++) {            durations[i] = (long)endTime[i] - startTime[i];        }         long maxFreeTime = 0;        // Initial gaps        maxFreeTime = Math.max(maxFreeTime, startTime[0]);        maxFreeTime = Math.max(maxFreeTime, eventTime - endTime[n - 1]);        for (int i = 1; i < n; i++) {            maxFreeTime = Math.max(maxFreeTime, (long)startTime[i] - endTime[i - 1]);        }         for (int i = 0; i <= n; i++) {            // Scenario 1: Pack prefix 0..i-1            long prefixDuration = 0;            int prefixCost = 0;            long currentIdealStart = 0;            for (int j = 0; j < i; j++) {                if (startTime[j] != currentIdealStart) {                    prefixCost++;                }                currentIdealStart += durations[j];            }            prefixDuration = currentIdealStart;            if (prefixCost <= k) {                long gap = (i < n) ? (long)startTime[i] - prefixDuration : (long)eventTime - prefixDuration;                maxFreeTime = Math.max(maxFreeTime, gap);            }             // Scenario 2: Pack suffix i..n-1            long suffixDuration = 0;            for (int j = i; j < n; j++) {                suffixDuration += durations[j];            }            int suffixCost = 0;            long currentIdealStartSuffix = eventTime - suffixDuration;            for (int j = i; j < n; j++) {                if (startTime[j] != currentIdealStartSuffix) {                    suffixCost++;                }                currentIdealStartSuffix += durations[j];            }            if (suffixCost <= k) {                long gap = (i > 0) ? (eventTime - suffixDuration) - endTime[i - 1] : eventTime - suffixDuration;                maxFreeTime = Math.max(maxFreeTime, gap);            }             // Scenario 3: Pack both            if (prefixCost + suffixCost <= k) {                long totalDuration = prefixDuration + suffixDuration;                maxFreeTime = Math.max(maxFreeTime, eventTime - totalDuration);            }        }         return (int)maxFreeTime;    }}

Complexity

Time

O(N^2). The main loop iterates `N+1` times. Inside this loop, calculating costs and durations for prefixes and suffixes involves nested loops that take O(N) time in total. This results in a quadratic time complexity.

Space

O(N) to store the durations of the meetings. This can be optimized to O(1) if durations are calculated on the fly.

Trade-offs

Pros

  • Conceptually straightforward, directly modeling the problem's scenarios.

  • Does not require complex data structures.

Cons

  • Inefficient for large inputs due to its quadratic time complexity.

  • Performs many redundant calculations for prefix/suffix costs and durations.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem