Merge Intervals
Programming Interview
Hard
4 views
Problem Description
Input provides {x}. Write function merge(intervals) and output merged intervals sorted.
Input Format
First line n. Next n lines: l r.
Output Format
Merged intervals lines.
Sample Test Case
Input:
4
1 3
2 6
8 10
9 11
Official Solution
import sys
lines=sys.stdin.read().splitlines()
if not lines: sys.exit(0)
n=int(lines[0].strip())
arr=[]
for i in range(1,1+n):
parts=(lines[i] if i<len(lines) else '').split()
if len(parts)<2: continue
arr.append((int(parts[0]),int(parts[1])))
arr.sort()
def merge(intervals):
if not intervals:
return []
out=[list(intervals[0])]
for l,r in intervals[1:]:
if l<=out[-1][1]:
if r>out[-1][1]:
out[-1][1]=r
else:
out.append([l,r])
return out
mrg=merge(arr)
out=[]
for l,r in mrg:
out.append(f'{l} {r}')
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!