Во многих компьютерных системах текущее время хранится в формате «UNIX-время» — количестве секунд от начала суток
В одной компьютерной системе проводили исследование загруженности. Для этого в течение месяца с момента UNIX-времени 1633046400 фиксировали и заносили в базу данных моменты старта и финиша всех процессов, действовавших в этой системе.
Вам необходимо определить, какое наибольшее количество процессов выполнялось в системе одновременно на неделе, начавшейся в момент UNIX-времени 1634515200, и в течение какого суммарного времени (в секундах) выполнялось такое наибольшее количество процессов.
Входные данные.
Первая строка входного файла содержит целое число N — общее количество процессов за весь период наблюдения. Каждая из следующих
Если в качестве времени старта указан ноль, это означает, что процесс был активен в момент начала исследования. Если в качестве времени завершения указан ноль, это означает, что процесс не завершился к моменту окончания исследования.
При совпадающем времени считается, что все старты и завершения процессов происходят одновременно, в начале соответствующей секунды. В частности, если время старта одного процесса совпадает с временем завершения другого и других стартов и завершений в этот момент нет, то количество активных процессов в этот момент не изменяется.
В ответе запишите два целых числа: сначала максимальное количество процессов, которые выполнялись одновременно на неделе, начиная с момента UNIX-времени 1634515200, затем суммарное количество секунд, в течение которых на этой неделе выполнялось такое максимальное количество процессов.
Ответ:
Заметим, что неделя в формате UNIX-времени — это
Если процесс начался до требуемой недели, а закончился после начала этой недели, будем сразу увеличивать значение
Приведём решение на языке Pascal.
var
n, count, sum_time, max_process, i: integer;
start_time, end_time, start_process, end_process: int64;
time_process: array[1..604800] of integer;
f: text;
begin
assign(f,'C:\26.txt');
reset(f);
readln(f, n);
start_time := 1634515199;
end_time := start_time + 604800;
count := 0;
while not eof(f) do begin
readln(f, start_process, end_process);
if (start_process < start_time) and ((end_process > start_time) or (end_process = 0)) then
count := count + 1;
if (start_process >= start_time) and (start_process <= end_time) then
time_process[start_process - start_time] := time_process[start_process - start_time] + 1;
if (end_process >= start_time) and (end_process <= end_time) then
time_process[end_process - start_time] := time_process[end_process - start_time] - 1;
end;
sum_time := 0;
max_process := 0;
for i := 1 to 604800 do begin
count := count + time_process[i];
if count > max_process then begin
max_process := count;
sum_time := 0;
end;
if count = max_process then sum_time := sum_time + 1;
end;
writeln(max_process, ' ', sum_time);
end.
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 7768 20.
Ответ: 7768 20.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open('26.txt')
n = int(f.readline())
start_time = 1634515199
end_time = start_time + 604800
count = 0
time_process = [0 for i in range(604801)]
for i in f:
start_process, end_process = i.split()
if (int(start_process) < start_time) and ((int(end_process) > start_time) or (int(end_process) == 0)):
count = count + 1
if (int(start_process) >= start_time) and (int(start_process) <= end_time):
time_process[int(start_process) - start_time] = time_process[int(start_process) - start_time] + 1
if (int(end_process) >= start_time) and (int(end_process) <= end_time):
time_process[int(end_process) - start_time] = time_process[int(end_process) - start_time] - 1
sum_time = 0
max_process = 0
for i in range(1, 604801):
count = count + time_process[i]
if count > max_process:
max_process = count
sum_time = 0
if count == max_process:
sum_time = sum_time + 1
print(max_process, sum_time)
Приведём другое решение Фефелова Сергея на языке Python.
f = open('26.txt')
n = int(f.readline())
L = []
w0 = 1634515200
w1 = w0 + 7*24*3600
for i in f:
st, en = [int(x) for x in i.split()]
if en == 0: en = w1
if st >= w1 or en <= w0: continue
L.extend([(max(st,w0), 1),(min(en,w1), -1)])
L.sort()
mxk = k = 0
for t, dk in L:
k += dk
if k > mxk: mxk, dt = k, 0
if k -dk == mxk: dt += t - t0
t0 = t
print(mxk, dt)