# Insert Interval
## Approach 1: Linear Search
- Uses a count `i` with `i < n` condition to avoid out of bound issue.
- A clear distinction between no overlapping and overlapping
- Merging intervals, not the most efficient, but it gets the job done without going into details.
```python
n = len(intervals)
new_start, new_end = new_interval
i = 0
res = []
# Case 1: No overlapping before merging intervals
while i < n and intervals[i][1] < new_start:
res.append(intervals[i])
i += 1
# Case 2: Overlapping and merging intervals
while i < n and new_end >= intervals[i][0]:
new_start = min(new_start, intervals[i][0])
new_end = max(new_end, intervals[i][1])
i += 1
res.append((new_start, new_end))
# Case 3: No overlapping after merging newInterval
while i < n:
res.append(intervals[i])
i += 1
return res
```