Advertisement
zemf4you

Untitled

Aug 6th, 2022
864
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.05 KB | None
  1. from collections import deque
  2.  
  3. class Segment:
  4.     def __init__(self, start: int, end: int):
  5.         self.start = start
  6.         self.end = end
  7.    
  8.     @staticmethod
  9.     def is_intersect(a, b):
  10.         return (a.start  <= b.start <= a.end or
  11.                 a.start  <= b.end   <= a.end) or \
  12.                (b.start <= a.start  <= b.end or
  13.                 b.start <= a.end    <= b.end)
  14.  
  15.     # use only if is_intersect
  16.     @classmethod
  17.     def concat(cls, a, b):
  18.         return cls(min(a.start, b.start), max(a.end, b.end))
  19.    
  20.     @property
  21.     def length(self):
  22.         return self.end - self.start
  23.  
  24.  
  25. n = int(input())
  26. segments = deque(Segment(*map(int, input().split())) for _ in range(n))
  27. out = []
  28. while segments:
  29.     x = segments.popleft()
  30.     for i, y in enumerate(segments):
  31.         if Segment.is_intersect(x, y):
  32.             segments[i] = Segment.concat(x, y)
  33.             break
  34.     else:
  35.         # if we don't use break in for, save oustanded segment
  36.         out.append(x)
  37.  
  38. print(len(out), sum(segment.length for segment in out))
  39.  
Advertisement
RAW Paste Data Copied
Advertisement