Microsoft Interview Question
InternsCountry: India
Here is the algorithm one can follow
S <- Input set
End_time = 0;
Subset_count = 0;
SubSet = {}
Sort the S with non decreasing order of end time
While exists at least one interval whose starttime > end_time
element <- Take the first in (non decreasing) order of end time
Subset_count ++;
SubSet.Add(element)
End_time = End_time of the element
Complexity : O(NlogN)
Time : O(1) or O(Result)
no, it would not, try this
{{1-10},{2-4}{5-8}}
if start with start time, we will only return 1 element, but the answer is 2 (can be found using endtime sorting)
this is a classical greedy algorithm on finding the largest set of nonoverlapping intervals
Here is the C# code for it.
Define the Intervals
public class Interval
{
public int intervalStart;
public int intervalEnd;
public override string ToString()
{
return string.Format("( Interval start at: {0}, IntervaleEnd at: {1} )", intervalStart.ToString(), intervalEnd.ToString());
}
}
Here is the subroutine to find out the max subset.
public static void FindMaxIntervals(Interval[] intervals)
{
if (intervals == null)
throw new Exception("intervals object undefined");
int length = intervals.Length;
for(int i = 0 ; i < length;i++)
{
if (intervals[i] == null)
throw new Exception(string.Format("{0}th interval is undefined", i));
}
Array.Sort<Interval>(intervals, delegate(Interval interval1, Interval interval2) { return interval1.intervalEnd.CompareTo(interval2.intervalEnd); });
//for (int i = 0; i < intervals.Length; i++)
//{
// Console.WriteLine(intervals[i].ToString());
//}
int intervalCount = 1;
int currentIntervalEnd = intervals[0].intervalEnd;
Console.WriteLine(intervals[0].ToString());
for (int i = 1; i < intervals.Length;i++)
{
if(intervals[i].intervalStart >= currentIntervalEnd)
{
intervalCount++;
currentIntervalEnd = intervals[i].intervalEnd;
Console.WriteLine(intervals[i].ToString());
}
}
Console.WriteLine("Count : {0}", intervalCount);
Console.ReadLine();
}
Here is the main method to generate the random intervals
public static void Main(string[] args)
{
Interval[] intervals = new Interval[10];
var rand = new Random();
for(int i = 0; i < 10; i++)
{
int j = rand.Next(0, 10);
intervals[i] = new Interval() { intervalStart = rand.Next(0, 20) - 5, intervalEnd = rand.Next(20, 40) - 5 };
}
FindMaxIntervals(intervals);
}
The idea follows:
1. use sweep line algorithm to find how many interval overlaps with each other.
2. use the number of overlap of intervals as the cost function. And Employ the steepest descent algorithm to remove the intervals with the largest number of intervals.
It is to remove the least intervals to guarantee the left intervals are not overlapped with each other. Therefore guarantee that S' is one of the maximal non-overlap subset of S.
Details follow: cpluspluslearning-petert.blogspot.co.uk/2015/06/data-structure-and-algorithm-find_19.html
sort the input set according to finish time in monotonically non-decreasing order.
Basically it is greedy algorithm where we are making sure that finishing time of
the set should be the least so that we can get the maximum non-overlapping intervals.
You can read more on this in "Introduction-Algorithms-Edition-Thomas-Cormen"
Take the finishing time of first set and compare that with rest of the set. If any other set is compatible i.e. starting time is more than finishing time
of first set then add to result. Now make the compatible set as current set and do the same.
's' is array of starting time and 'f' finishing time
- aka[1] June 11, 2015