in_chainz

Untitled

Nov 25th, 2018
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.78 KB | None | 0 0
  1. n = int(input())
  2. ev = []
  3. a = []
  4. for i in range(n):
  5.     l, r = map(int, input().split())
  6.     a.append((l, r))
  7.     ev.append((l, 1, i))
  8.     ev.append((r, -1, i))
  9. ev.sort()
  10. bal = 0
  11. INF = 10 ** 18
  12. mn = INF
  13. one = -1
  14. two = -1
  15. last = 0
  16. for i in range(2 * n):
  17.     bal += ev[i][1]
  18.     if bal > 0 and ev[i][1] == -1 and i - 1 >= 0 and ev[i - 1][1] == 1:
  19.         if mn > ev[i][0] - ev[i - 1][0] and ev[i][0] - ev[i - 1][0] > 0:
  20.             mn = ev[i][0] - ev[i - 1][0]
  21.             one = ev[i][2]
  22.             two = ev[i - 1][2]
  23. if mn == INF:
  24.     print(0)
  25. elif one != two:
  26.     print(one + 1, two + 1)
  27. else:
  28.     l, r = a[one][0], a[one][1]
  29.     for i in range(n):
  30.         if i != one and a[i][0] <= l and a[i][1] >= r:
  31.             ans = i
  32.             break
  33.     print(ans + 1, one + 1)
Advertisement
Add Comment
Please, Sign In to add comment