Bạt che nắng (THT TP 2018)

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Thời gian:

Python 3 5.0s

Bộ nhớ:

Python 3 1G

Tác giả:

Small

Dạng bài

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Hiếu đi dự đám cưới ở một nhà hàng trong thành phố. Trời nắng nên con đường hành lang đi từ nhà hàng ra bãi giữ xe được che bởi các tấm bạt có kích thước khác nhau (đường hành lang là đường thẳng). Nhưng vì các chú bảo vệ lo nhận và giữ xe nên che các tấm bạt rất lộn xộn chỗ thì khít, chỗ thì chồng lên nhau, chỗ thì hở ra. Hiếu muốn tìm đoạn đường dài nhất trên đường mình đi được che kín bởi các tấm bạt.

Cho \(N\) cặp số [\(L_i,R_i\)], \(i=1..N\) (\(0 \le L_i,R_i\le 60000\)) là vị trí đầu và vị trí cuối của mỗi tấm bạt theo chiều dài hành lang.

Yêu cầu: Viết chương trình tìm độ dài lớn nhất của đoạn đường được che kín bởi các tấm bạt.

Input

Dòng đầu chứa một số nguyên \(N\) (\(1< N \le 10000\)) là số lượng tấm bạt.
\(N\) dòng tiếp theo mỗi dòng biểu diễn vị trí của mỗi tấm bạt theo chiều dài hành lang là \(L_i\) và \(R_i\) (mỗi số cách nhau một dấu cách, \(L_i < R_i\)).

Output

Ghi ra một số nguyên duy nhất theo yêu cầu trên.

Example

Test 1

Input

Output

Note

Giải thích: Đoạn đường được che kín dài nhất là từ vị trí 6 đến 19, được che bởi 3 tấm bạt là: \((6;8), (7;12),(11, 19)\)

Bình luận

Hint

# nhập n là số lượng tấm bạc
n = int(input())
lim = int(6e4+10)
road = [0]*lim
# duyệt for để đánh dấu các vị trí bắt đầu và kết thúc của mỗi tấm bạc
for _ in range(n):
    l, r = map(int,input().split())
    road[l] += 1
    road[r] -= 1
# khởi tạo biến cnt là số lượng tấm bạc
cnt = 0
che = [0]*(lim)
for i in range(0,lim):
    # cập nhập số lượng tấm bạc đang có cnt
    cnt += road[i]
    # khi nào thì vị trí i được bạc che
    if cnt >0:
        che[i] = True
    else:
        che[i] = False
# tìm đoạn được bạc che dài nhất, tức là tìm đoạn bằng True dài nhất trong che
Max = 0
chieudaiht = 0

for i in range(lim):
    if che[i]: 
        chieudaiht += 1
        Max = max(Max, chieudaiht)
    else: 
        chieudaiht = 0

print(Max)

6

SPyofgame 4:32 p.m. 4 Tháng 3, 2021

Bài này làm offline \(O(n)\) được và online \(O(n \log n)\)