Skip to content

Instantly share code, notes, and snippets.

@TomaQ
Created February 21, 2019 06:11
Show Gist options
  • Save TomaQ/5884e4c2e27f344d03de6561f39f5fca to your computer and use it in GitHub Desktop.
Save TomaQ/5884e4c2e27f344d03de6561f39f5fca to your computer and use it in GitHub Desktop.
// This one seems pretty abstract and probably depends a lot from interview to interview
// but here's my interpretation without any feedback from the interviewer
// and trying to do it in 15 mins
public class Firework
{
public int StartTime {get;set;}
public int Duration {get;set;}
}
public bool WereFireworksAlwaysPresent(List<Firework> fireworks)
{
//general check stuff here
// sort fireworks based on start time (probably a better way)
fireworks = fireworks.OrderBy(x => x.StartTime).ToList();
int farthestEndTime = 0;
// start at the second firework since the festival starts with the first one
for(int i = 1; i < fireworks.Length; i++)
{
// logic here might be a little iffy
// we're seeing what is the latest end time for fireworks so far
int previousEndTime = fireworks[i-1].StartTime + Duration;
if(previousEndTime > farthestEndTime)
farthestEndTime = previousEndTime;
// check if by the time the firework ended if the next one started or if a previous one already went off
if(farthestEndTime < fireworks[i].StartTime)
return false;
}
return true;
}
public int MaxNumOfFireworksPresent(List<Firework> fireworks)
{
// general check stuff here
//this is pretty much a "find the max number of intervals overlapping" question
var start = fireworks.OrderBy(x => x.StartTime).ToList();
var end = fireworks.OrderBy(x => x.StartTime + Duration).ToList();
int currentOverlap = 0;
int maxOverlap = 0;
int startIndex = 0;
int endIndex = 0;
while(startIndex < start.Length && endIndex < end.Length)
{
if(start[startIndex] < end[endIndex])
{
currentOverlap++;
if(currentOverlap > maxOverlap)
maxOverlap = currentOverlap;
startIndex++;
}
else
{
currentOverlap--;
endIndex++;
}
}
return maxOverlap;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment