Во многих компьютерных системах текущее время хранится в формате «UNIX-время» — количестве секунд от начала суток
В одной компьютерной системе проводили исследование загруженности. Для этого в течение месяца с момента UNIX-времени 1633046400 фиксировали и заносили в базу данных моменты старта и финиша всех процессов, действовавших в этой системе.
Вам необходимо определить, какое наибольшее количество процессов выполнялось в системе одновременно на неделе, начавшейся в момент UNIX-времени 1633305600, и в течение какого суммарного времени (в секундах) выполнялось такое наибольшее количество процессов.
Входные данные.
Первая строка входного файла содержит целое число N — общее количество процессов за весь период наблюдения. Каждая из следующих
Если в качестве времени старта указан ноль, это означает, что процесс был активен в момент начала исследования. Если в качестве времени завершения указан ноль, это означает, что процесс не завершился к моменту окончания исследования.
При совпадающем времени считается, что все старты и завершения процессов происходят одновременно, в начале соответствующей секунды. В частности, если время старта одного процесса совпадает с временем завершения другого и других стартов и завершений в этот момент нет, то количество активных процессов в этот момент не изменяется.
В ответе запишите два целых числа: сначала максимальное количество процессов, которые выполнялись одновременно на неделе, начиная с момента UNIX-времени 1633305600, затем суммарное количество секунд, в течение которых на этой неделе выполнялось такое максимальное количество процессов.
Ответ:
Заметим, что неделя в формате 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 := 1633305600;
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.
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 5000 46.
Ответ: 5000 46.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение на языке Python.
f = open("26 (7).txt")
n = int(f.readline())
start_time = 1633305600
end_time = start_time + 604800
count = 0
time_process = [0 for i in range(0, 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())
x0 = 1633046400
y0 = x0 + 31*24*60*60
pr = [0]*(y0-x0+1)
for i in range(n):
a, b = map(int, f.readline().split())
a = max(a, x0)
if b == 0:
pr[a-x0] += 1
else:
pr[a-x0] += 1
pr[b-x0] -= 1
for i in range(1, len(pr)):
pr[i] += pr[i-1]
x1 = 1633305600
y1 = x1 + 7*24*60*60
mx = t = 0
for i in range(x1-x0, y1-x0):
if pr[i] > mx:
mx = pr[i]
t = 0
if pr[i] == mx:
t += 1
print(mx, t)
Приведём решение Юрия Красильникова на языке Python.
f = open('26.txt')
начало,конец = 1633305600,1633305600+7*24*3600 # начало и конец недели
f.readline() # пропускаем количество записей
dic={} # в словаре ключ - момент времени, значение - на сколько изменяется число процессов
for s in f:
t1,t2=map(int,s.split()) # время начала и время конца процесса
if t1 < начало: dic[начало] = dic.get(начало,0)+1
elif t1 < конец: dic[t1]=dic.get(t1,0)+1
if t2!=0:
if t2 < начало: dic[начало] = dic.get(начало,0)-1
elif t2 < конец: dic[t2]=dic.get(t2,0)-1
a = sorted([[t,dic[t]] for t in dic if dic[t]!=0]) # сортировка по времени начала/конца
for k in range(1,len(a)): a[k][1] += a[k-1][1] # сумма с накоплением
# в списке a элементы - пары [момент времени, количество процессов]
a.append([конец,0]) # если последний интервал в неделе с макс. количеством процессов
макспроц = max([x[1] for x in a]) # макс. количество процессов
сумма = sum([a[k][0]-a[k-1][0] for k in range(1,len(a)) if a[k-1][1]==макспроц])
print(макспроц,сумма)