Polycarp Training (Codeforces 1165B)
Tags: Greedy, sortings

Polycarp wants to train before another programming competition. During the first day of his training he should solve exactly $$$1$$$ problem, during the second day — exactly $$$2$$$ problems, during the third day — exactly $$$3$$$ problems, and so on. During the $$$k$$$-th day he should solve $$$k$$$ problems.Polycarp has a list of $$$n$$$ contests, the $$$i$$$-th contest consists of $$$a_i$$$ problems. During each day Polycarp has to choose exactly one of the contests he didn't solve yet and solve it. He solves exactly $$$k$$$ problems from this contest. Other problems are discarded from it. If there are no contests consisting of at least $$$k$$$ problems that Polycarp didn't solve yet during the $$$k$$$-th day, then Polycarp stops his training.How many days Polycarp can train if he chooses the contests optimally?

Input: The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of contests.The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the number of problems in the $$$i$$$-th contest.

Output: Print one integer — the maximum number of days Polycarp can train if he chooses the contests optimally.


Sample Inputs:
4
3 1 4 1

3
1 1 1

5
1 1 1 2 2

Sample Outputs:
3

1

2

Solution (Python):
input()
r = 0
for x in sorted(map(int, input().split())):
    r += x > r
print(r)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
p = 1
c = 0
for i in a:
    if i >= p:
        p += 1
        c += 1
print(c)

Solution (Python):
num_contests = int(input())
questions_per_contest = [int(x) for x in input().split()]
questions_per_contest.sort()
day = 1
for i in range(num_contests):
    if questions_per_contest[i] >= day:
        day += 1
print(day - 1)