## Merging

``````    +------+               +----------------+
|      |               |                |
+---------------+      +-------------+      |
|   |      |    |      |   |         |      |
+---+------+----+      +---+---------+------+

figure. 1                figure. 2
``````
• figure. 1

An interval contains another interval, the merged one is the bigger one.

• figure. 2

An interval overlaps another interval, the merged one is smaller start and bigger end

``````function merge(i1. i2)

return { start = MIN(i1.start, i2.start), end = MAX(i1.end, i2.end) }
``````

## Merge using a stack [Loop invariant]

Assume that all intervals into a stack and all intervals are sorted by `start`. The top two intervals in the stack are the smallest in `start`.

If the top two cant be merged into one, the smaller one must cant be merged with any other intervals. in another word, the smaller one can be put into final result set.

``````stack with sorted intervals

while stack is not empty

smallest = stack.pop()
secondary smallest = stack.pop()

if can merge (overlap or contain)
merged = merge(smallest, secondary smallest)
stack.push(merged)

else

put smallest into results

stack.push(secondary smallest)
``````