Đoạn bao nhau 2

Cho N đoạn thẳng trên trục số với các điểm đầu a_i và điểm cuối b_i là những số nguyên trong khoảng -1000..1000, a_i < b_i, i = 1..n.  Liệt kê tối đa K đoạn bao nhau.

DOAN.INP	DOAN.OUT		Dữ liệu vào: tệp văn bản DOAN.INP: xem bài trước Dữ liệu ra: tệp văn bản DOAN.OUT Dòng đầu tiên:  số tự nhiên K. Tiếp đến là K dòng, mỗi dòng chứa một số tự nhiên là chỉ số của đoạn trong dãy tìm được. Các chỉ số được liệ kê theo trật tự bao nhau từ lớn đến nhỏ. Thí dụ này cho biết tối đa có 3 đoạn bao nhau là các đoạn 1, 5  và 2:  [-1,12] Ê [8,11] Ê [8,10].
6 -1 12 8 10 17 18 2 7 8 11 13 20	3 1 5 2

Thuật toán

Giống bài Đoạn bao nhau 1. Để có danh sách đoạn bao nhau ta dùng mảng trỏ t[1..n],  t[i] trỏ đến đoạn j là đoạn nằm trong đoạn i và c[j] đạt giá trị max.

Độ phức tạp: N².

(*  Pascal  *)

uses crt;

const MN = 1001; bl = #32; nl = #13#10;

fn = 'doan.inp'; gn = 'doan.out';

type

Doan = record  a,b: integer; id: integer;  end;

MD1 = array[0..MN] of Doan;

MI1 = array[0..MN] of integer;

var f,g: text;

d: MD1;

t: MI1; { tro truoc }

n: integer;

imax, k: integer;

procedure Doc; tự làm

function SanhDoan(x,y: Doan): integer; tự làm

procedure QSortB(t,p: integer): tự làm

procedure XuLi;

var c: mi1;

i,j: integer;

begin

  imax := 1;

  for i := 1 to n do

  begin

    c[i] := 0; t[i] := 0;

    for j := i-1 downto 1 do

    begin

      if (d[j].b <= d[i].a) then break;

      if (d[j].a >= d[i].a) then

        if (c[j] > c[i]) then

        begin c[i] := c[j]; t[i] := j end;

    end;

    c[i] := c[i] + 1;

    if (c[imax] < c[i]) then imax := i;

  end;

  k := c[imax];

end;

procedure Path(i: integer);

begin

  if (i = 0) then exit;

  writeln(g,d[i].id); Path(t[i]);

end;

procedure Ghi;

begin

   assign(g,gn); rewrite(g); writeln(g,k);

   path(imax); close(g);

end;

BEGIN

 Doc; QSortB(1,n); XuLi; Ghi; readln;

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH