Auction Market
InterviewTime limit1sMemory limit512 MB
Buyers in fixed order scan items left to right and bid on the first item they can afford or outbid, and we count how many items end up with a bidder.
- Level
Medium6 of 10
- Topics
- Greedy, Binary search, Segment tree, Implementation
- Solved
- No attempts yet
Problem
On a particular day, N items numbered from 1 to N are sold at an auction market, and the starting price of the ith item is Si. There are M potential buyers numbered from 1 to M who want to take part in the auction, and the budget of the jth potential buyer is Bj.
One by one, from the 1st potential buyer to the Mth potential buyer, each potential buyer inspects the items one by one from the 1st to the Nth and decides whether he is able to bid on that item. The jth potential buyer is able to bid on the ith item if and only if at least one of the following conditions holds.
- No one has bid on the ith item yet and Bj ≥ Si.
- Someone has bid on the ith item and Bj is strictly larger than the current highest bid for that ith item.
If the jth potential buyer is able to bid on the ith item, he bids Bj on that ith item and stops inspecting the remaining items, that is, he ignores the (i + 1)th to Nth items. With this behavior, each potential buyer bids on at most 1 item. A potential buyer may also fail to bid on any item at all, for example when his budget is too low.
At the end of the day, after all the potential buyers have either placed their bid or inspected all items, the highest bid for each item is determined and the items are sold to the respective highest bidders. Items with no bidder are not sold.
Find how many items are successfully sold at the end of the day.
Input
Input begins with a line containing an integer: N (1 ≤ N ≤ 100 000), the number of items to be sold at the auction market. The second line contains N integers: Si (1 ≤ Si ≤ 109), the starting price of each item. The third line contains an integer M (1 ≤ M ≤ 100 000), the number of potential buyers. The fourth line contains M integers: Bj (1 ≤ Bj ≤ 109), the budget of each potential buyer.
Output
Output in one line an integer, the number of items that are successfully sold at the end of the day.