Given a pair of numbers (intervals) we want to merge overlapping intervals.
Example:
Given (1, 3), (2, 5), (5, 8), (7,9), (10,11) we can merge overlapping intervals and return (1,5), (5,9), (10,11)
Solution:
To solve this problem we can check the ending number of an interval with the starting number of another interval and if it is greater then we need to merge them in to one interval by taking the start number from the first interval and end number from second interval.
example (1,3) , (2,5) we see that 3 > 2 so we can merge it in to (1,5)
Next we need to chose the right data structure to store a given interval.
Well we can create our own data structure called Range by implementing a class.
class Range
{
public int start { get; set; }
public int end { get; set; }
public Range(int start, int end)
{
this.start = start;
this.end = end;
}
}
Then we can chose another data structure to store the collection of intervals.
We can use Linked Lists, Stacks…
For this example lets us use Stack<> as they are relatively simple to understand.
We need to create a stack of ranges, Stack<Range>.
So what we are going to do is we pick up one range from the given list of ranges and we see if it is in the stack if not we add it to the stack.
Then we peak at the top element of the stack and see if the ending number of this interval is greater than the starting number of the current interval we are in the given list. If so we merge them in to one interval by taking the start number from the range we peaked and end number from current interval in the list. We pop the top element in the stack and push this newly created range to the stack.
public List<Range> solution(List<Range> ranges) {
Stack<Range> stack = new Stack<Range>();
foreach(Range range in ranges) {
if (stack.Count == 0) {
stack.Push(range);
}
else {
Range r = stack.Peek();
if (r.end > range.start) {
r.end = Math.Max(r.end,range.end);
stack.Pop();
stack.Push(r);
}
else
stack.Push(range);
}
}
return stack.ToList<Range>();
}
}