حل تمرین بازه بازی در برره کوئرا با پایتون

حل تمرین بازه بازی در برره کوئرا با پایتون

در این نوشته به روش حل یکی از سوالات برنامه نویسی وب‌سایت کوئرا می‌پردازیم.

حل تمرین بازه بازی در برره کوئرا با پایتون

می‌دانیم بازه بازی جایگاه ویژه‌ای در میان اهالی برره دارد. شیرفرهاد و کَیانوش به دل طبیعت رفته بودند که تصمیم گرفتند بازه بازی کنند! در این بازی n بازه وجود دارد و برنده کسی‌ست که اندازه‌ی بزرگترین مجموعه‌ی برره‌پسند را بیابد. یک مجموعه از بازه‌ها برره‌پسند است اگر و فقط اگر تمامی اعضای آن متمایز باشند و به ازای هر دو بازه مثل a و b، یا a درون $b$ قرار گیرد یا بلعکس. شما به عنوان طرفدار شیرفرهاد اندازه‌ی بزرگترین مجموعه‌ی برره‌پسند را بیابید تا او برنده شود. دقت کنید اندازه‌ی یک مجموعه برابر تعداد اعضای آن است.

ورودی

در خط اول n آمده است. در هر یک از n خط بعدی a_i​، شروع بازه‌ی $i$اُم و b_i​ پایان بازه‌ی iاُم داده شده است.

خروجی

در تنها خط خروجی اندازه بزرگ‌ترین مجموعه‌ی برره‌پسند را چاپ کنید.

مثال

ورودی نمونه 1

3
3 4
2 5
1 6

خروجی نمونه 1

3

ورودی نمونه 2

5
10 30
20 40
30 50
10 60
30 40

خروجی نمونه 2

3

توضیح نمونه 2: در این نمونه اندازه بزرگ‌ترین مجموعه‌ی برره پسند برابر 3 است و بازه‌های 3و4و5 (به ترتیب ورودی) این مجموعه را می‌سازند.

ورودی نمونه 3

6
1 4
1 5
1 6
1 7
2 5
3 5

خروجی نمونه 3

5

توضیح نمونه 3: در این نمونه تنها کافیست که اولین بازه (به ترتیب ورودی) را از مجموعه حذف کنیم، در نتیجه 5 بازه دیگر بزرگترین مجموعه برره پسند را تشکیل می‌دهند.

کد پایتون سوال تمرین بازه بازی در برره

import sys
import bisect

maxn = 100100
inf = 2e18 + 13

# ورودی و تنظیمات اولیه
n = int(input())
v = []
arr = []

dp = [inf] * maxn

# خواندن ورودی و پردازش داده‌ها
for _ in range(n):
    a, b = map(int, input().split())
    v.append((a, -b))

# مرتب‌سازی و ساخت آرایه
v.sort()
for i in range(n):
    arr.append(-v[i][1])

arr.reverse()

ans = 0

# محاسبه پاسخ
for i in range(n):
    k = bisect.bisect_right(dp, arr[i])
    dp[k] = arr[i]
    ans = max(ans, k + 1)

print(ans)

منبع سوال: کوئرا

اگر نیاز به حل تمرین‌های دیگری از کوئرا دارید در بخش نظرات همین نوشته برای ما بنویسید.