ICPC PACNW 2016 H - Paint

View as PDF

Submit solution

Points: 7
Time limit: 1.8s
Memory limit: 256M

Problem type

You are painting a fence with n sections, numbered from 1 to n. There are k artists, each willing to paint their design on a specific portion of the fence. However, artists will never agree to have their section painted over, so they will only paint their portion of the fence if no one else will paint any part of it.

You want to select a set of painters that does not conflict to minimize the number of unpainted sections.


The first line contains two positive integers n (1 \le n \le 10^{18}) and k (1 \le k \le 200\,000).

Each of the next k lines contains two positive integers a_i and b_i, where 1 \le a_i \le b_i \le n, indicating that the ith artist wants to paint all sections between section a_i and section b_i, inclusive.


Print, on a single line, a single integer indicating the minimum number of unpainted sections.

Sample Input

8 3
1 3
2 6
5 8

Sample Output

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported


There are no comments at the moment.