DjangoBB LoFi version

Полная версия: Не понимаю условий задания

Начало » Python для новичков » Не понимаю условий задания

udeep

Дек. 15, 2019 17:39:34

Условия:
N intervals were colored on the number axis. We know the coordinate of the left and the right ends of each of these intervals (Li and Ri). Find the sum of the lengths of parts of the number axis, colored evenly in a single layer.
Use merge sort algorithm for sorting.

Пример:
Sample Input:
3
1 4
7 8
2 5
Sample Output:
3

Не понимаю, почему в примере ответ = 3. - IMHO, в один слой окрашены: 1, 5, 7 и 8, что в итоге = 4
М.б. загадка кроется в “evenly”, но логики пока не вижу…

py.user.next

Дек. 16, 2019 02:55:02

udeep
Не понимаю, почему в примере ответ = 3. - IMHO, в один слой окрашены: 1, 5, 7 и 8, что в итоге = 4
М.б. загадка кроется в “evenly”

evenly - равномерно, ровно (где-то может быть и “чётно”, но в данном случае нет).

Равномерно в одинарном слое закраски.

(1, 4), (7, 8), (2,5) после сортировки превращаются в (1, 2), (2, 4), (4, 5), (5, 7), (7, 8)

(1, 2) - закрашен один раз
(2, 4) - закрашен два раза
(4, 5) - закрашен один раз
(5, 7) - не закрашен
(7, 8) - закрашен один раз

Считаем длины одноразово закрашенных
(1, 2) - длина 1
(4, 5) - длина 1
(7, 8) - длина 1

1 + 1 + 1 = 3

udeep

Дек. 16, 2019 07:23:27

Спасибо.
Признаю. - Затупил

   
n = int(input())
line = []
for _ in range(n):
    i, j = map(int, input().split())
    line.extend([(i, -1), (j, 1)])
  
r = n = 0
for v, k in sorted(line):
    if n == 1:
        r += v - z
    z = v
    n -= k
      
print(r)