Here’s a fun challenge from Interview Cake. It’s best to check out the problem’s description on the site, but the basics of it are take an array of start/stop times and reduce them down to the bare minimum needed to show which time blocks are occupied.
For example, given:
[(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)]
your function would return:[(0, 1), (3, 8), (9, 12)]
There were a few edge cases to account for in this problem, such as ranges that completely span others. The result below covered every case proposed and does so without iterating through the array multiple times.
I start by sorting the array by start time, then iterate through the array, comparing the current element to the next. If there is no overlap, we do nothing and move on to the next element.
If we find the current meeting runs longer than the next, (completely overlaps), we delete the next meeting. If we find the current meeting’s end time overlaps with the next meetings start time, we can combine those. (e.g., [1,4] and [3,5] become [1,5]).
If we match one of the two above criteria, we need to re-iterate the loop with the same element to see if it overlaps the following meeting as well.
#array = [ [0, 1], [0, 3] [3, 5], [4, 8], [10, 12], [9, 10] ]
array = [ [1, 10], [2, 6], [3, 5], [7, 9] ]
def condense_ranges(a)
a.sort!{|a, b| a[0] <=> b[0]}
i = 0
while i < a.length - 1
curr_meeting = a[i]
next_meeting = a[i+1]
#if earlier meeting runs longer than the next just delete the next meeting
if curr_meeting[1] >= next_meeting[1]
a.delete_at(i+1)
#earlier meeting ends after or exactly when the next begins, we have overlap
elsif curr_meeting[1] >= next_meeting[0]
a[i] = [ curr_meeting[0], next_meeting[1] ]
a.delete_at(i+1)
else
#if no overlap, check the next element
i += 1
end
end
#the remaining elements are the solution
puts a
end
condense_ranges(array)
My soup.io.