Genome annotation is fundamentally interval arithmetic. When several transcript
isoforms of the same gene are collapsed into a single gene model, their exons overlap and must be
merged into a non-redundant set — this is what bedtools merge does, and it is the operation behind
computing gene length for RNA-seq normalisation. Getting the boundary conditions right (does an
interval ending at 100 overlap one starting at 100?) is a genuine source of off-by-one bugs in
production pipelines.
Statement
You are given a set of exon intervals as half-open ranges [start, end) on a single
chromosome.
Merge every group of overlapping or directly adjacent intervals into a single interval. Two intervals
are adjacent when one ends exactly where the next begins.
Print the merged intervals sorted by start coordinate ascending, one per line, as start end separated
by a single space. On the final line, print the total merged length.
Input — read from standard input
| Variable | Type | Description |
|---|---|---|
n
line 1
|
int |
The number of intervals
1 <= n <= 1000
|
intervals
line 2..n+1
|
str |
One interval per line as two space-separated integers, start and end
0 <= start < end <= 1000000
|
These variables are already read for you in the starter code on the right.
Output
str merged intervals one per line sorted by start, then a final line with the total merged length
Sample Cases
4
100 200
150 300
400 500
480 520
100 300
400 520
320
3
10 20
20 30
30 40
10 40
30
Submit also runs your code against 5 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.
Constraints
1 <= n <= 1000- Intervals are half-open:
[start, end)includesstartbut excludesend - Intervals sharing an endpoint (
[10, 20)and[20, 30)) are adjacent and must be merged - Input intervals arrive in arbitrary order
Further Reading
- Sort by start coordinate first; everything else follows in a single sweep.
- Merge when the next interval's start is
<=the current end — using<would leave adjacent
intervals unmerged. - Total merged length is the sum of
(end - start)over the merged set, not over the input.