Insert Interval

LeetCode

Commonly asked at:Google Meta LinkedIn

Insert Interval

Given a list of already-sorted, non-overlapping intervals and a new interval, insert it and merge if necessary.

Example

Input: existing [1,3] [6,9], new [2,5] Output: [1,5] [6,9]

Approach

Three passes in one sweep: first copy every interval that ends before the new one starts (no overlap, untouched), then absorb every interval that overlaps the new one by expanding the new interval's own start/end to cover them, then copy the remaining intervals that start after the (now-expanded) new interval ends.

Input format

Line 1: number of existing intervals R Next R lines: start end Last line: the new interval, start end

Print the result, one start end pair per interval, separated by |.

Not solved yet

Ctrl+Enter

Editor

r = int(input())
intervals = [list(map(int, input().split())) for _ in range(r)]
new_start, new_end = map(int, input().split())
result = []
i, n = 0, len(intervals)
# TODO: 1) copy non-overlapping before, 2) merge overlapping into new interval, 3) copy the rest

r = int(input())
intervals = [list(map(int, input().split())) for _ in range(r)]
new_start, new_end = map(int, input().split())
result = []
i, n = 0, len(intervals)
# TODO: 1) copy non-overlapping before, 2) merge overlapping into new interval, 3) copy the rest

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Editor

r = int(input())
intervals = [list(map(int, input().split())) for _ in range(r)]
new_start, new_end = map(int, input().split())
result = []
i, n = 0, len(intervals)
# TODO: 1) copy non-overlapping before, 2) merge overlapping into new interval, 3) copy the rest

r = int(input())
intervals = [list(map(int, input().split())) for _ in range(r)]
new_start, new_end = map(int, input().split())
result = []
i, n = 0, len(intervals)
# TODO: 1) copy non-overlapping before, 2) merge overlapping into new interval, 3) copy the rest

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Community Discussions

No discussions yet

Be the first to start a conversation.