Merge Weekly Time Intervals

Question

The candidate is asked to write a function that merges overlapping weekly time intervals into consolidated intervals.

Codemia · Accepted Answer

To merge weekly time intervals, we first need to sort the intervals based on their start times. After sorting, we can iterate through the list and merge overlapping intervals by comparing the end time of the current interval with the start time of the next interval.

1. **Sort the intervals**: Use a sorting algorithm to arrange the intervals based on their start times.
2. **Initialize a merged list**: Start with the first interval in the merged list.
3. **Iterate through the intervals**: For each subsequent interval, check if it overlaps with the last interval in the merged list. If it does, merge them by updating the end time. If not, append the current interval to the merged list.

Here is a Python implementation of the algorithm:
```python
def merge_intervals(intervals):
    if not intervals:
        return []
    # Sort intervals by the start time
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for current in intervals[1:]:
        last_merged = merged[-1]
        # Check for overlap
        if current[0] <= last_merged[1]:
            # Merge intervals
            last_merged[1] = max(last_merged[1], current[1])
        else:
            # No overlap, add to merged list
            merged.append(current)
    return merged
```

The time complexity of this algorithm is O(n log n) due to the sorting step, where n is the number of intervals. The space complexity is O(n) in the worst case, where no intervals overlap and all are added to the merged list.

Consider edge cases such as:
- Intervals that are completely overlapping.
- Intervals that touch at the edges (e.g., [1, 3] and [3, 5]).
- An empty list of intervals should return an empty list.

While the current solution is efficient, if the intervals are guaranteed to be sorted beforehand, we can skip the sorting step, reducing the time complexity to O(n). Additionally, if memory usage is a concern, we could merge intervals in place rather than using a separate list.

Merge Weekly Time Intervals

Nextdoor

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Nextdoor Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string