Merge Intervals With Decimal Endpoints and List the Gaps Between Them
Company: Palantir
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given a list of closed intervals on the number line. Endpoints are not limited to integers: they may also be decimal numbers. First merge every group of overlapping intervals. Then build a second list that holds the gaps between consecutive merged intervals, that is, the stretches of the line between two merged intervals that no input interval covers.
### Function Signature
```python
def merge_with_gaps(intervals: list[list[float]]) -> dict[str, list[list[float]]]:
```
Return a dictionary with exactly two keys, `"merged"` and `"gaps"`.
### Rules
- `intervals[i] = [start, end]` with `start <= end` is the closed interval of all `x` with `start <= x <= end`. An interval with `start == end` is a single point.
- Two intervals overlap when they share at least one point. Intervals that only touch also overlap: `[1, 2]` and `[2, 3.5]` merge into `[1, 3.5]`.
- `"merged"` is the list of intervals whose union equals the union of all input intervals, with no two of them overlapping or touching, sorted by `start` in increasing order.
- `"gaps"` holds, for each pair of consecutive merged intervals `[a, b]` and `[c, d]`, the interval `[b, c]`: the uncovered stretch strictly between `b` and `c`, reported by its endpoints. Gaps are listed in increasing order. With `m` merged intervals there are `m - 1` gaps; the parts of the line before the first and after the last merged interval are not gaps.
- Every number in the output is an endpoint copied from the input, so values compare exactly. If `intervals` is empty, both lists are empty.
### Constraints
- `0 <= len(intervals) <= 10^4`
- `-10^9 <= start <= end <= 10^9`, and every endpoint is a finite integer or decimal number.
- The input is in no particular order and may contain duplicate intervals.
### Examples
**Example 1**
```text
Input: intervals = [[1.5, 3], [8, 10], [2, 4.25], [12.5, 13], [9.5, 11]]
Output: {"merged": [[1.5, 4.25], [8, 11], [12.5, 13]], "gaps": [[4.25, 8], [11, 12.5]]}
```
`[1.5, 3]` and `[2, 4.25]` overlap, as do `[8, 10]` and `[9.5, 11]`. Nothing covers the line between 4.25 and 8, or between 11 and 12.5.
**Example 2**
```text
Input: intervals = [[0, 1], [1, 2.5], [0.25, 0.75], [-3.5, -1]]
Output: {"merged": [[-3.5, -1], [0, 2.5]], "gaps": [[-1, 0]]}
```
`[0.25, 0.75]` lies inside `[0, 1]`, and `[0, 1]` touches `[1, 2.5]`, so all three merge into `[0, 2.5]`.
**Example 3**
```text
Input: intervals = [[5, 5]]
Output: {"merged": [[5, 5]], "gaps": []}
```
A single merged interval leaves no gap.
Overview: Merge a list of closed intervals whose endpoints may be decimal numbers, treating intervals that only touch as overlapping, and then list the uncovered gaps between consecutive merged intervals. It tests interval reasoning, precise boundary rules and exact handling of non-integer endpoints.
You are given a list `intervals` of closed intervals on the number line. Endpoints are not limited to integers: they may also be decimal numbers. First merge every group of overlapping intervals. Then build a second list that holds the gaps between consecutive merged intervals, that is, the stretches of the line between two merged intervals that no input interval covers.
Return a dictionary with exactly two keys, `"merged"` and `"gaps"`, each mapping to a list of `[start, end]` pairs (in JavaScript an object, in Java a `java.util.Map<String, java.util.List<java.util.List<Double>>>`, in C++ a `std::map<std::string, std::vector<std::vector<double>>>`).
### Rules
- `intervals[i] = [start, end]` with `start <= end` is the closed interval of all `x` with `start <= x <= end`. An interval with `start == end` is a single point.
- Two intervals overlap when they share at least one point. Intervals that only touch also overlap: `[1, 2]` and `[2, 3.5]` merge into `[1, 3.5]`.
- `"merged"` is the list of intervals whose union equals the union of all input intervals, with no two of them overlapping or touching, sorted by `start` in increasing order.
- `"gaps"` holds, for each pair of consecutive merged intervals `[a, b]` and `[c, d]`, the interval `[b, c]`: the uncovered stretch strictly between `b` and `c`, reported by its endpoints. Gaps are listed in increasing order. With `m` merged intervals there are `m - 1` gaps; the parts of the line before the first and after the last merged interval are not gaps.
- Every number in the output is an endpoint copied from the input, so values compare exactly. If `intervals` is empty, both lists are empty.
- Endpoints are double-precision floating-point numbers (`double` in Java and C++). Their absolute value is at most 10^9, so no value exceeds 2^31 - 1.
### Example 1
```text
Input: intervals = [[1.5, 3], [8, 10], [2, 4.25], [12.5, 13], [9.5, 11]]
Output: {"merged": [[1.5, 4.25], [8, 11], [12.5, 13]], "gaps": [[4.25, 8], [11, 12.5]]}
```
`[1.5, 3]` and `[2, 4.25]` overlap, as do `[8, 10]` and `[9.5, 11]`. Nothing covers the line between 4.25 and 8, or between 11 and 12.5.
### Example 2
```text
Input: intervals = [[0, 1], [1, 2.5], [0.25, 0.75], [-3.5, -1]]
Output: {"merged": [[-3.5, -1], [0, 2.5]], "gaps": [[-1, 0]]}
```
`[0.25, 0.75]` lies inside `[0, 1]`, and `[0, 1]` touches `[1, 2.5]`, so all three merge into `[0, 2.5]`.
### Constraints
- `0 <= len(intervals) <= 10^4`
- `-10^9 <= start <= end <= 10^9`, and every endpoint is a finite integer or decimal number.
- The input is in no particular order and may contain duplicate intervals.
Constraints
- 0 <= len(intervals) <= 10^4
- -10^9 <= start <= end <= 10^9, and every endpoint is a finite integer or decimal number.
- The input is in no particular order and may contain duplicate intervals.
Examples
Input: ([],)
Expected Output: {'merged': [], 'gaps': []}
Explanation: Empty input: both lists are empty.
Input: ([[5, 5]],)
Expected Output: {'merged': [[5, 5]], 'gaps': []}
Explanation: Source example 3: one single-point interval is one merged interval and leaves no gap.
Hints
- Closed intervals that only touch, such as [1, 2] and [2, 3.5], overlap and belong to the same merged interval, and a single point [x, x] counts as a full interval.
- A merged interval ends at the largest end among the intervals it absorbs, which need not be the end of the last interval you examined.
- Gaps come only from consecutive merged intervals: m merged intervals give exactly m - 1 gaps, and each gap's endpoints are merged endpoints copied unchanged.