PTIT127C spoj ptit- Bố trí phòng họp

Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT127C/

Nội dung bài viết

1. Đề bài PTIT127C spoj
- Input
- Output
2. Gợi ý PTIT127C spoj
3. Code tham khảo PTIT127C spoj Pascal
- Code 1
- Code 2

1. Đề bài PTIT127C spoj

Có n cuộc họp đánh số từ 1 đến n đăng ký làm việc tại một phòng hội thảo. Cuộc họp i cần được bắt đầu ngay sau thời điểm s_ivà kết thúc tại thời điểm f_i. Hỏi có thể bố trí phòng hội thảo phục vụ được nhiều nhất bao nhiêu cuộc họp, sao cho khoảng thời gian làm việc của hai cuộc họp bất kỳ là không giao nhau.

Input

Dòng đầu tiên chứa số nguyên dương n ( n <= 10000)
Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên dương s_i, f_i (s_i < f_i <= 32000) ( 1 <= i <= n).

Output

Dòng đầu tiên ghi số K là số các cuộc họp được chấp nhận phục vụ

2. Gợi ý PTIT127C spoj

– Các bạn dùng sắp xếp theo chiều tăng dần của B[i] (1<=i<=N) rồi dùng thuật toán tham lam tìm dãy cuộc hợp từ 1..i thỏa mãm B[i]>A[i]>=B[1..i-1].

3. Code tham khảo PTIT127C spoj Pascal

Code 1

const   fi='';
        nmax=10000;
type
        data=longint;
        dulieu=record
                u,v:data;
        end;

var
        f:text;
        A:array[1..nmax] of dulieu;
        n:data;

procedure docfile;
var     i:data;
begin
        assign(f,fi); reset(f);
        readln(f,n);
        for i:=1 to n do
                readln(f,a[i].u,a[i].v);
        close(f);
end;

procedure sort(l,r: longint);
      var
         i,j,x: longint;
         y:dulieu;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2].v;
         repeat
           while a[i].v<x do
            inc(i);
           while x<a[j].v do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;


procedure xuli;
var     i,j:data;
        res,cuoi,k:data;
begin
        res:=0; cuoi:=0;

        i:=1;
        while i<=n do
                begin
                        if (a[i].u>=cuoi) and (a[i].v>cuoi) then
                                begin
                                        inc(res);
                                        cuoi:=a[i].v;
                                end;
                        inc(i);
                end;
        writeln(res);
end;

begin
        docfile;
        sort(1,n);
        xuli;
end.

const fi='';

nmax=10000;

type

data=longint;

dulieu=record

u,v:data;

end;

var

f:text;

A:array[1..nmax] of dulieu;

n:data;

procedure docfile;

var i:data;

begin

assign(f,fi); reset(f);

readln(f,n);

for i:=1 to n do

readln(f,a[i].u,a[i].v);

close(f);

end;

procedure sort(l,r: longint);

var

i,j,x: longint;

y:dulieu;

begin

i:=l;

j:=r;

x:=a[(l+r) div 2].v;

repeat

while a[i].v<x do

inc(i);

while x<a[j].v do

dec(j);

if not(i>j) then

begin

y:=a[i];

a[i]:=a[j];

a[j]:=y;

inc(i);

j:=j-1;

end;

until i>j;

if l<j then

sort(l,j);

if i<r then

sort(i,r);

end;

procedure xuli;

var i,j:data;

res,cuoi,k:data;

begin

res:=0; cuoi:=0;

i:=1;

while i<=n do

begin

if (a[i].u>=cuoi) and (a[i].v>cuoi) then

begin

inc(res);

cuoi:=a[i].v;

end;

inc(i);

end;

writeln(res);

end;

begin

docfile;

sort(1,n);

xuli;

end.

Code 2

Const   Fi='';
        Fo='';
Type    Data    =       record
                Site, Start, Finish: Longint;
        End;
Var     F:              Text;
        A:              Array[1..10000] of Data;
        N, I, J, Sum, Last:     Longint;
Procedure       Init;
        Begin
                Assign(f,fi);
                Reset(f);
                Readln(f,n);
                For i:=1 to n do
                        Readln(f,a[i].Start,a[i].Finish);
                close(f);
                Sum:=0;
                Last:=0;
                i:=1;
        End;
Procedure sort(l,r: longint);
      var
         i,j,x: longint;
         y:data;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2].Finish;
         repeat
           while a[i].Finish<x do
            inc(i);
           while x<a[j].Finish do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;
Procedure       Process;
        Begin
                Sort(1,n);
                While i<=n do
                        Begin
                                If (a[i].Start>=Last) and (a[i].Finish>last) then
                                        Begin
                                                Inc(Sum);
                                                Last:=a[i].Finish;
                                                Inc(k);
                                        End;
                                Inc(i);
                        End;
        End;
Procedure       Print;
        Begin
                Assign(f,fo);
                Rewrite(f);
                Writeln(f,Sum);
                Close(f);
        End;
Begin
        Init;
        Process;
        Print;
End.

Const Fi='';

Fo='';

Type Data = record

Site, Start, Finish: Longint;

End;

Var F: Text;

A: Array[1..10000] of Data;

N, I, J, Sum, Last: Longint;

Procedure Init;

Begin

Assign(f,fi);

Reset(f);

Readln(f,n);

For i:=1 to n do

Readln(f,a[i].Start,a[i].Finish);

close(f);

Sum:=0;

Last:=0;

i:=1;

End;

Procedure sort(l,r: longint);

var

i,j,x: longint;

y:data;

begin

i:=l;

j:=r;

x:=a[(l+r) div 2].Finish;

repeat

while a[i].Finish<x do

inc(i);

while x<a[j].Finish do

dec(j);

if not(i>j) then

begin

y:=a[i];

a[i]:=a[j];

a[j]:=y;

inc(i);

j:=j-1;

end;

until i>j;

if l<j then

sort(l,j);

if i<r then

sort(i,r);

end;

Procedure Process;

Begin

Sort(1,n);

While i<=n do

Begin

If (a[i].Start>=Last) and (a[i].Finish>last) then

Begin

Inc(Sum);

Last:=a[i].Finish;

Inc(k);

End;

Inc(i);

End;

Procedure Print;

Begin

Assign(f,fo);

Rewrite(f);

Writeln(f,Sum);

Close(f);

End;

Begin

Init;

Process;

Print;

End.

PTIT127C spoj ptit- Bố trí phòng họp

1. Đề bài PTIT127C spoj

Input

Output

2. Gợi ý PTIT127C spoj

3. Code tham khảo PTIT127C spoj Pascal

Code 1

Code 2

Bài viết liên quan

Trả lời Hủy