Au au ua ui ya!!
InterviewTime limit2sMemory limit512 MB
Given N segments [x, y] already sorted by x, compute the total length covered by their union on the number line.
- Level
Medium4 of 10
- Topics
- Intervals, Sorting, Array, Implementation
- Solved
- No attempts yet
Problem
Au au ua ui ya!! Ua a a a a a a a a a a a a a a a a
We are going to draw several line segments on the number line, ua a a a a a a a a!!
It is also possible to draw segments that overlap, a u u o o o o o o o o o o i ya!!!!1
When all the segments have been drawn, what is the total length of the segments drawn on the number line, a a a o o o o o i o i i ya?!!!
Input
The first line gives the number N of segments to draw on the number line, a u ua u i ya!!. (1 ≤ N ≤ 100,000)
From the second line, N lines each give a pair of integers (x, y) representing coordinates, u o a a a a a a a a a a a a.
This means a segment is drawn on the interval [x, y] (the interval including x and y), yu a a u u i ya.
The coordinates are given in increasing order of x, and if x is equal, in increasing order of y, u u o a a a a o o o. (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)
Output
When all N segments have been drawn, output the total length of the segments drawn on the number line, a a o o i e e a u a i a ya a a a a a a i ya!!!