闭区间问题pascal

更新时间：2018-03-12 00:03:26 185次访问

题目描述

数轴上有n个开区间（ai，bi）。选择其中尽可能多个开区间，使这些区间两两无公共点

注：开区间（ai，bi）表示数轴上ai，bi之间所有的数但不包括ai，bi

输入

第一行：n

第二行到第n+1行：ai，bi

输出

样例输入

5
1 6
2 5
4 7
4 8
7 8

样例输出

2

提示

1<n<=10000

0<ai<bi<=2^31-1

我简单写了个参考:

/// 闭区间问题
/// /whoami1978 2018/3/3
var
 n, ct, i: integer;
 a: array [1 .. 10000, 1 .. 2] of longint;
 pend: longint;

procedure m_sort;
var
 i, j: integer;
 t: longint;
begin
 for i := 1 to n do
   for j := 1 to n - i do
     if a[j, 2] < a[j + 1, 2] then
     begin
       t := a[j, 1];
       a[j, 1] := a[j + 1, 1];
       a[j + 1, 1] := t;
       t := a[j, 2];
       a[j, 2] := a[j + 1, 2];
       a[j + 1, 2] := t;
     end;

end;

begin
 readln(n);
 for i := 1 to n do
   readln(a[i, 1], a[i, 2]);
 m_sort;
 pend := -1;
 ct := 0;
 for i := 0 to n do
   if pend < a[i, 1] then
   begin
     inc(ct);
     pend := a[i, 2];
   end;
 writeln(ct);

end.