ps:problems:boj:1689
겹치는 선분
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 1689 |
문제명 | 겹치는 선분 |
레벨 | 골드 4 |
분류 |
스위핑, 그리디 |
시간복잡도 | O(nlogn) |
인풋사이즈 | n<=1,000,000 |
사용한 언어 | Python 3.11 |
제출기록 | 265796KB / 4056ms |
최고기록 | 2244ms |
해결날짜 | 2023/05/30 |
풀이
- 강의실 배정과 같은 유형. 풀이는 그쪽 참고.
코드
"""Solution code for "BOJ 1689. 겹치는 선분".
- Problem link: https://www.acmicpc.net/problem/1689
- Solution link: http://www.teferi.net/ps/problems/boj/1689
Tags: [Sweeping]
"""
import sys
RIGHT = 0
LEFT = 1
def main():
N = int(sys.stdin.readline())
coord = []
for _ in range(N):
s, e = [int(x) for x in sys.stdin.readline().split()]
coord.append((s, LEFT))
coord.append((e, RIGHT))
count = 0
answer = max(
(count := count + (1 if type_ == LEFT else -1))
for _, type_ in sorted(coord)
)
print(answer)
if __name__ == '__main__':
main()
ps/problems/boj/1689.txt · 마지막으로 수정됨: 2023/05/30 02:35 저자 teferi
토론