Score : 400 points
There are N islands lining up from west to east, connected by N-1 bridges.
The i-th bridge connects the i-th island from the west and the (i+1)-th island from the west.
One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:
Request i: A dispute took place between the a_i-th island from the west and the b_i-th island from the west. Please make traveling between these islands with bridges impossible.
You decided to remove some bridges to meet all these M requests.
Find the minimum number of bridges that must be removed.
Input is given from Standard Input in the following format:
N M a_1 b_1 a_2 b_2 : a_M b_M
Print the minimum number of bridges that must be removed.
5 2 1 4 2 5
1
The requests can be met by removing the bridge connecting the second and third islands from the west.
9 5 1 8 2 7 3 5 4 6 7 9
2
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
4