% https://open.kattis.com/problems/intervalscheduling
% 1s
% 1.9 Easy

% Picat

% The algorithm is from Johan Sannemo's Algorithmic Problem Solving, p176:
% The basic idea is to sort the instances and then
% start with the interval with the leftmost right interval
%
import util.
main :-
    garbage_collect(500_000_000),
    Ns = [T.split(" ").map(to_int): T in read_file_lines().tail],
    % println(ns=Ns),
    % interval_scheduling(Ns,Res),
    s(Ns.sort(2),-1,[],Res),
    % writeln(Res),
    writeln(Res.len).

/*
   Some random/harder instances.
   Note: Use garbage_collect/1, otherwise it takes longer to generate the numbers than
   to solve them...
   Here are some results. The first time is the generation of the numbers, the second is
   the solve time.

m = 5
n = 100000

CPU time 0.019 seconds.

generation_ok

CPU time 0.055 seconds.

365

m = 6
n = 1000000

CPU time 0.164 seconds.

generation_ok

CPU time 1.119 seconds.

1213

m = 7
n = 10000000

CPU time 2.386 seconds.

generation_ok

CPU time 18.53 seconds.

3763

*/
main2 :-
   member(M,1..7),
   garbage_collect(1600_000_000),
   println(m=M),
   _ = random2(),
   N = 10**M,
   println(n=N),
   Max = 10**9,
   % Ns = [ [P,P+random(1,Max div 2)] : _ in 1..N, P = random(0,Max)],
   time(gen(N,Max,[],Ns)),
   println(generation_ok),
   time(interval_scheduling(Ns,Res)),
   writeln(Res.len),
   nl,
   fail.

% For generating an .inp file
main3 :-
   _ = random2(),
   N = 10**5,
   println(N),
   Max = 10**9,
   gen(N,Max,[],Ns),
   foreach([A,B] in Ns)
     printf("%d %d\n",A,B)
   end,
   nl.
  

gen(0,_,L,L).
gen(I,Max,L0,[[A,B]|L]) :-
  I > 0,
  A = random(0,Max),
  B = A + random(1,Max div 2),
  gen(I-1,Max,L0,L).

s([],_,R,R).
s([[A,B]|Ss],H0,R0,R) :-
    (A >= H0 ->
      append(R0,[[A,B]],R1),
      H1 = B
    ;
      R1 = R0,
      H1 = H0
    ),
    s(Ss,H1,R1,R).

/*
s([],_,R,R).
s([[A,B]|Ss],H0,R0,[[A,B]|R]) :-
    A >= H0,
    s(Ss,B,R0,R).
s([[A,B]|Ss],H0,R0,R) :-
    A < H0,
    s(Ss,H0,R0,R).
*/

interval_scheduling(Ns,Res) :-
    s(Ns.sort(2),-1,[],Res).