Validate interval list balanced

Question

Given a list of intervals, determine if the intervals are balanced, meaning that for every interval, the number of overlapping intervals on the left is equal to the number of overlapping intervals on the right. The input will be a list of intervals represented as pairs of integers, and the output should be a boolean value indicating whether the list is balanced or not.

Codemia · Accepted Answer

The problem at hand is to determine if a list of intervals is balanced, meaning the number of overlapping intervals on the left is equal to the number on the right for each interval. This can be effectively approached using a **sweep line algorithm** combined with a **counting mechanism**. The sweep line technique is suitable here because we can process intervals in a sorted manner, allowing us to efficiently count overlaps as we traverse through the list. The key insight is that for each interval, we can keep track of how many intervals start or end before and after it, thus determining the balance.

1. **Sort the Intervals**: First, sort the intervals by their start times. If the start times are the same, sort by end times.

2. **Count Overlaps**: Use two passes through the sorted intervals:
   - In the first pass, for each interval, count how many intervals end before it (these are on the left).
   - In the second pass, count how many intervals start after it (these are on the right).

3. **Check Balance**: For each interval, compare the counts from both passes. If they are not equal for any interval, return false.

### Example:
Given intervals: `[(1, 3), (2, 4), (3, 5)]`
- After sorting: `[(1, 3), (2, 4), (3, 5)]`
- For interval (1, 3): Left = 0, Right = 2
- For interval (2, 4): Left = 1, Right = 1
- For interval (3, 5): Left = 2, Right = 0
Since left and right counts are not equal for (1, 3) and (3, 5), the result is false.

Here is the Python implementation of the above approach:
```python
def validate_intervals_balanced(intervals):
    # Sort intervals by start time
    intervals.sort(key=lambda x: (x[0], x[1]))
    n = len(intervals)
    left_counts = [0] * n
    right_counts = [0] * n

# Count left overlaps
    for i in range(n):
        for j in range(i):
            if intervals[j][1] > intervals[i][0]:  # j ends after i starts
                left_counts[i] += 1

# Count right overlaps
    for i in range(n):
        for j in range(i + 1, n):
            if intervals[j][0] < intervals[i][1]:  # j starts before i ends
                right_counts[i] += 1

# Check if balanced
    for i in range(n):
        if left_counts[i] != right_counts[i]:
            return False
    return True
```
This implementation efficiently counts the overlaps using nested loops, which is manageable given the constraints.

The time complexity of this solution is O(n^2) due to the nested loops used for counting overlaps. Each interval is compared with others to count left and right overlaps. In terms of space complexity, it is O(n) because we store the left and right counts in separate lists. Given the typical constraints of interval problems, this solution is reasonable, though we can consider optimizing further if needed.

1. **Empty List**: If the intervals list is empty, it should return True as there are no intervals to compare.
2. **Single Interval**: A single interval should also return True since there are no overlaps.
3. **No Overlapping Intervals**: If there are intervals that do not overlap at all, they should return True as left and right counts will be zero for all.
4. **All Intervals Overlapping**: If all intervals overlap with each other, they should return False as the counts will not balance out.
5. **Invalid Input**: Handle cases where intervals are not in the correct format or contain invalid numbers (e.g., negative intervals). These should be validated before processing.

Validate interval list balanced

Shopify

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Shopify 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