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];
}
}
}