Why Did the Cow Cross the Road (Silver)#10535
Farmer John's cows are trying to learn how to cross the road safely and efficiently. Remembering the old "why did the chicken cross the road?" joke, they figure that chickens must be experts at crossing roads, so they set off in search of chickens who can help them.
As it turns out, chickens are very busy creatures and have only limited time to help the cows. There are chickens on the farm, conveniently numbered , and chicken is willing to help a cow only at precisely time t_i. The cows, never in a hurry, have more flexible schedules. There are cows on the farm, conveniently numbered , where cow can cross the road at any time between A_j and B_j, inclusive.
Using a "buddy system," each cow would like to find a chicken to help her cross the road. Their schedules are compatible if A_j \le t_i \le B_j.
If each cow can be paired with at most one chicken and each chicken with at most one cow, help compute the maximum possible number of cow-chicken pairs.
The first line contains c~(1 \le c \le 20000) and n~(1 \le n \le 20000). The next lines contain the values t_1, \ldots, t_c, and the next lines contain A_j and B_j~ (A_j \le B_j) for j = 1, \ldots, n. The values A_j, B_j, and t_i are all non-negative integers not exceeding 10^9 and are not necessarily distinct.
Print the maximum possible number of cow-chicken pairs.
Ejemplo 1