In a movie festival $$$n$$$ movies will be shown. You know the starting and ending time of each movie. What is the maximum number of movies you can watch entirely?
The first input line has an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$): the number of movies.
After this, there are $$$n$$$ lines that describe the movies. Each line has two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a \leq b \leq 10^9$$$): the starting and ending times of a movie.
Print one integer: the maximum number of movies.
3 3 5 4 9 5 8
2
You have to process $$$n$$$ tasks. Each task has a duration and a deadline, and you will process the tasks in some order one after another. Your reward for a task is $$$d-f$$$ where $$$d$$$ is its deadline and $$$f$$$ is your finishing time. (The starting time is $$$0$$$, and you have to process all tasks even if a task would yield negative reward.)
What is your maximum reward if you act optimally?
The first input line has an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$): the number of tasks.
After this, there are $$$n$$$ lines that describe the tasks. Each line has two integers $$$a$$$ and $$$d$$$ ($$$1 \leq a,d \leq 10^6$$$): the duration and deadline of the task.
Print one integer: the maximum reward.
3 6 10 8 15 5 12
2
There are $$$n$$$ children who want to go to a Ferris wheel, and your task is to find a gondola for each child. Each gondola may have one or two children in it, and in addition, the total weight in a gondola may not exceed $$$x$$$. You know the weight of every child.
What is the minimum number of gondolas needed for the children?
The first input line contains two integers $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) and $$$x$$$ ($$$1 \leq x \leq 10^9$$$): the number of children and the maximum allowed weight.
The next line contains n integers $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \leq p_i \leq x$$$): the weight of each child.
Print one integer: the minimum number of gondolas.
4 10 7 2 3 9
3
There are $$$n$$$ applicants and $$$m$$$ free apartments. Your task is to distribute the apartments so that as many applicants as possible will get an apartment.
Each applicant has a desired apartment size, and they will accept any apartment whose size is close enough to the desired size.
The first input line has three integers $$$n$$$, $$$m$$$ ($$$1 \leq n,m \leq 2\cdot 10^5$$$), and $$$k$$$ ($$$0 \leq k \leq 10^9$$$): the number of applicants, the number of apartments, and the maximum allowed difference.
The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$): the desired apartment size of each applicant. If the desired size of an applicant is $$$x$$$, they will accept any apartment whose size is between $$$x-k$$$ and $$$x+k$$$.
The last line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$): the size of each apartment.
Print one integer: the number of applicants who will get an apartment.
4 3 5 60 45 80 60 30 60 75
2
You have a stick of length $$$x$$$ and you want to divide it into $$$n$$$ sticks, with given lengths, whose total length is $$$x$$$.
On each move you can take any stick and divide it into two sticks. The cost of such an operation is the length of the original stick.
What is the minimum cost needed to create the sticks?
The first input line has two integers $$$x$$$ ($$$1 \leq x \leq 10^9$$$) and $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$): the length of the stick and the number of sticks in the division.
The second line has $$$n$$$ integers $$$d_1,d_2,\ldots,d_n$$$ ($$$1 \leq d_i \leq x, \sum d_i = x$$$): the length of each stick in the division.
Print one integer: the minimum cost of the division.
8 3 2 3 3
13