Merge Intervals

Reverse a String

Two Sum

Sort and merge every overlapping or touching interval into a disjoint list.

Given a list of closed intervals `[start, end]`, merge every pair that overlaps or touches and return the disjoint intervals sorted by start value.

**Input / output**
- Input: `intervals: [integer, integer][]`
- Output: merged intervals in ascending order

**Examples**
1. `[[1,3],[2,6],[8,10],[15,18]]` returns `[[1,6],[8,10],[15,18]]`.
2. `[[1,4],[4,5]]` returns `[[1,5]]` because the endpoints touch.

**Constraints**
- `1 <= intervals.length <= 10,000`
- `-100,000 <= start <= end <= 100,000`
- Input intervals may be unsorted and duplicated.

**Follow-up**
If intervals arrived one at a time in sorted order, how would you merge them without storing the entire input?

- Given an array of intervals where each interval is represented as `[start, end]`, merge overlapping intervals.
- The goal is to return a list of non-overlapping intervals that cover all intervals in the input array.

Understanding the Problem

- Sort the intervals based on their starting values.
- This will make it easier to detect overlaps by ensuring that any overlapping intervals are adjacent.

Sort Intervals by Start Time

- Create an empty list `merged` to store the merged intervals.
- The list will eventually contain only the non-overlapping intervals.

Initialize Merged Intervals List

- For each interval, check if it overlaps with the last interval in the `merged` list.
- If it does overlap, merge the intervals by extending the end of the last interval in `merged`.
- If it doesn’t overlap, simply add it to `merged`.

Iterate Through Sorted Intervals

- After processing all intervals, return the `merged` list which contains only non-overlapping intervals.

Return Merged Intervals

- Edge cases include:
  - Only one interval, which should be returned as-is.
  - Non-overlapping intervals, where each interval is added to `merged` without modification.
  - Intervals that completely overlap each other.