3439. Reschedule Meetings for Maximum Free Time I

EasyView on LeetCode

Array Greedy Sorting

Time: O(n)

Space: O(n)

Intuition

Find maximum length increasing subsequence with constraint that adjacent pair differs by at most d.

Algorithm

1DP: dp[i] = max LIS ending at i. Transition: dp[i] = 1 + max(dp[j]) where j < i, nums[j] < nums[i], nums[i]-nums[j] <= d.

Common Pitfalls

•Standard LIS DP with additional difference constraint. O(n^2) or segment tree for O(n log n).

3439.cs

// Approach: Sliding window of k meetings; compute max gap after removing k consecutive meetings.
// Time: O(n) Space: O(n)

public class Solution
{
    public int MaxFreeTime(int eventTime, int k, int[] startTime, int[] endTime)
    {
        int[] gaps = GetGaps(eventTime, startTime, endTime);
        int windowSum = gaps.Take(k + 1).Sum();
        int ans = windowSum;

        for (int i = k + 1; i < gaps.Length; i++)
        {
            windowSum += gaps[i] - gaps[i - k - 1];
            ans = Math.Max(ans, windowSum);
        }

        return ans;
    }

    private int[] GetGaps(int eventTime, int[] startTime, int[] endTime)
    {
        int[] gaps = new int[startTime.Length + 1];
        gaps[0] = startTime[0];
        for (int i = 1; i < startTime.Length; ++i)
            gaps[i] = startTime[i] - endTime[i - 1];
        gaps[startTime.Length] = eventTime - endTime[endTime.Length - 1];
        
        return gaps;
    }
}

Was this solution helpful?