Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from collections import deque
- class Segment:
- def __init__(self, start: int, end: int):
- self.start = start
- self.end = end
- @staticmethod
- def is_intersect(a, b):
- return (a.start <= b.start <= a.end or
- a.start <= b.end <= a.end) or \
- (b.start <= a.start <= b.end or
- b.start <= a.end <= b.end)
- # use only if is_intersect
- @classmethod
- def concat(cls, a, b):
- return cls(min(a.start, b.start), max(a.end, b.end))
- @property
- def length(self):
- return self.end - self.start
- n = int(input())
- segments = deque(Segment(*map(int, input().split())) for _ in range(n))
- out = []
- while segments:
- x = segments.popleft()
- for i, y in enumerate(segments):
- if Segment.is_intersect(x, y):
- segments[i] = Segment.concat(x, y)
- break
- else:
- # if we don't use break in for, save oustanded segment
- out.append(x)
- print(len(out), sum(segment.length for segment in out))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement