/ Coding

The Insider's Guide to Sliding Window and Scheduling

Problem Statement (asked at Uber)

There is a meeting scheduled in an office that lasts for time t and starts at time 0.
In between the meeting there are n presentations whose start and end times are given i.e. the ith presentation starts at s[i] and ends at e[i]-1. The presentations do not overlap with each other.
You are given k, the maximum number of presentations that you can reschedule keeping the original order intact.
Note that the duration of the presentation can’t be changed. You can only change the start and end time.

Your task is to maximize the longest time period in which there is no presentation scheduled during the meeting.

Constraints :-
1<=t<=1, 000, 000, 000
0<=k<=n
1<=n<=100, 000
e[i]<=s[i+1], 0<=i <n-1
s[i] < e[i] for 0<=i<=n-1

Possible Solution

We could utilize the sliding window concept by rescheduling only k entries at once i.e. the maximum number of presentations to be rescheduled.

using System;

namespace Preparations
{
    class Program
    {
        public static void Main(string[] args)
        {
            /* Problem Statement:
There is a meeting scheduled in an office that lasts for time t and starts at time 0. 
In between the meeting there are n presentations whose start and end times are given i.e. 
the ith presentation starts at s[i] and ends at e[i]-1. The presentations do not overlap with each other. 
You are given k, the maximum number of presentations that you can reschedule keeping the original order intact. 
Note that the duration of the presentation can’t be changed. You can only change the start and end time. 
Your task is to maximize the longest time period in which there is no presentation scheduled during the meeting.

            Constraints :-
            1<=t<=1, 000, 000, 000
            0<=k<=n
            1<=n<=100, 000
            e[i]<=s[i+1],   0<=i <n-1
            s[i] < e[i] for 0<=i<=n-1
            
            */

            // Meeting Time in minutes
            var meetingTimeInMinutes = 180;

            // Maximum Number of presentations to reschedule
            var maxReschedules = 2;

            // Number of presentations
            var numberOfPresentations = 3;

            // Start of Presentation
            TimeSpan[] startEntries = { new TimeSpan(8, 0, 0), new TimeSpan(8, 0, 0), new TimeSpan(9, 15, 0), new TimeSpan(10, 0, 0) };
            // End of Presentation
            TimeSpan[] endEntries = { new TimeSpan(8, 30, 0), new TimeSpan(9, 30, 0), new TimeSpan(10, 30, 0) };

            // TODO: Add breaking conditions for the constraints using Bouncer Pattern

            // Find the initial Free Time before the first meeting started
            var currentMeetingCount = 0;
            var freeTime = GetPreviousFreeTime(startEntries, endEntries, 1);
            var maxFreeTime = freeTime;

            for (var index = 1; index <= numberOfPresentations; index++)
            {
                // No presentations to reschedule
                if (maxReschedules == 0)
                {
                    // Free time variable initialized already with Previous Free Time
                    if (index != 1)
                    {
                        freeTime = GetPreviousFreeTime(startEntries, endEntries, index);
                    }
                    // Update Max Free time 
                    maxFreeTime = UpdateMaxFreeTIme(freeTime, maxFreeTime);

                    // Reset the free time to consider next values alone
                    freeTime = TimeSpan.Zero;
                }
                else // k > 0
                {
                    // Remove first free time using the concept of sliding window
                    if (currentMeetingCount == maxReschedules)
                    {
                        // Remove Previous and Current Meeting time of the first index of the sliding window
                        var removalIndex = index - maxReschedules;
                        freeTime = freeTime - (GetPreviousFreeTime(startEntries, endEntries, removalIndex)
                                               + GetCurrentMeetingTime(startEntries, endEntries, removalIndex));
                        currentMeetingCount--;
                    }
                    // Update the current meeting time
                    var currentMeetingTime = GetCurrentMeetingTime(startEntries, endEntries, index);
                    freeTime += currentMeetingTime;
                    currentMeetingCount++;
                }

                // Get the next free time for the current index
                var nextFreeTime = GetNextFreeTime(startEntries, endEntries, index, meetingTimeInMinutes);
                freeTime += nextFreeTime;

                // Update Max Free Time
                maxFreeTime = UpdateMaxFreeTIme(freeTime, maxFreeTime);
            }

            // Maximum Free Time (Minutes)
            Console.WriteLine("Maximum Free Time (Minutes): " + maxFreeTime.TotalMinutes);
            Console.ReadLine();
        }

        /// <summary>
        /// Updates Max Free Time if <paramref name="freeTime"/> is greater than the <paramref name="maxFreeTime"/>
        /// </summary>
        /// <param name="freeTime">Free Time</param>
        /// <param name="maxFreeTime">Maximum Free Time</param>
        /// <returns>Updated Maximum Free Time</returns>
        private static TimeSpan UpdateMaxFreeTIme(TimeSpan freeTime, TimeSpan maxFreeTime)
        {
            // Check for Setting MaxFreeTime
            if (freeTime > maxFreeTime)
            {
                maxFreeTime = freeTime;
            }
            return maxFreeTime;
        }

        /// <summary>
        /// Get Meeting Time for the current index <paramref name="i"/>
        /// </summary>
        /// <param name="start">Start Time Array</param>
        /// <param name="end">End Time Array</param>
        /// <param name="i">Current Index</param>
        /// <returns>Current Meeting Time</returns>
        private static TimeSpan GetCurrentMeetingTime(TimeSpan[] start, TimeSpan[] end, int i)
        {
            return end[i - 1] - start[i];
        }

        /// <summary>
        /// Get the next free time for the current index <paramref name="i"/>
        /// </summary>
        /// <param name="start">Start Time Array</param>
        /// <param name="end">End Time Array</param>
        /// <param name="i">Current Index</param>
        /// <param name="t">Total Time in Minutes</param>
        /// <returns>Current Meeting Time</returns>
        private static TimeSpan GetNextFreeTime(TimeSpan[] start, TimeSpan[] end, int i, int t)
        {
            // Last Meeting
            if (i == end.Length)
            {
                return start[0].Add(TimeSpan.FromMinutes(t)) - end[i-1];
            }
            return start[i+1] - end[i - 1];
        }

        /// <summary>
        /// Get the previous free time for the current index <paramref name="i"/>
        /// </summary>
        /// <param name="start">Start Time Array</param>
        /// <param name="end">End Time Array</param>
        /// <param name="i">Current Index</param>
        /// <returns>Current Meeting Time</returns>
        private static TimeSpan GetPreviousFreeTime(TimeSpan[] start, TimeSpan[] end, int i)
        {
            // First Meeting
            if (i == 1)
            {
                return start[i] - start[0];
            }
            return start[i] - end[i - 2];
        }
    }
}
The Insider's Guide to Sliding Window and Scheduling
Share this

Subscribe to Coding Today

Popular queries