Did you know that the yummy golden triangle was introduced in India as early as 13th century ? By the way, I'm referring to the popular South Asian snack, Samosa. I guess its hard to code while thinking of Samosa, especially if you are very hungry now ; so lets not get in to any recipe or eating game. 

You have N  boxes of Samosas, where each box is a cube. To pack a box, you need to use a rubber band ( pseudo-circular, elastic band ) by placing it around the box ( along 4 faces of the cube ).  A (R1,R2)-rubber band has initial radius R1 and it can stretch at max to radius R2 without breaking. You can pack a cubical box of side length L using a rubber band of circumference 4 * L ( see Notes for clarity). Given M rubber bands along with their initial radius and max radius, we need to match ( assign ) some rubber bands to boxes. A box needs at least one rubber band to pack it and of course, each rubber band can be used to pack at most one box. Find the maximum number of boxes we can pack.

------ Notes ------ 
A pseudo-circular rubber band having a radius R has circumference of 2 * K * R , where K is a constant = 22 / 7. So, a (R1,R2) rubber band can be used to pack a cubical box of side length L, only if 2 * K * R1 ≤ 4 * L ≤ 2 * K * R2

------ Input ------ 

First line contains an integer T ( number of test cases, around 20 ). T cases follow. Each test case starts with an integer N ( number of boxes, 1 ≤ N ≤ 1000 ). Next line contains N integers, the side lengths L of the N boxes ( 1 ≤ L ≤ 100,000,000 ). Next line contains an integer M ( number of rubber bands, 1 ≤ M ≤ 1000 ). Each of the next M lines contains two integers R1 R2 ( 1 ≤ R1 ≤ R2 ≤ 100,000,000 ), separated by a space.

------ Output ------ 

For each test case, output the maximum number of boxes you can pack, in a new line.

----- Sample Input 1 ------ 
1
4
10 20 34 55
4
7 14
7 21
14 21
7 35
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
Only 1 test case here, and a possible answer can be, using (7,14) rubber band to pack box L = 10, and using (7,35) rubber band to pack box L = 55. We cannot pack more than 2 boxes.

Source: codechef | Difficulty: HARD
Tags: Complete search

Sorting

Greedy algorithms


Solutions:
for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = int(input())
	d = []
	for y in range(c):
		(e, f) = input().split()
		d.append((int(f), int(e)))
	used = [False] * c
	b.sort()
	d.sort()
	count = 0
	for i in range(a):
		p = 7 * b[i]
		for j in range(c):
			if used[j]:
				continue
			(l, r) = (11 * d[j][1], 11 * d[j][0])
			if l <= p and p <= r:
				used[j] = True
				count += 1
				break
	print(count)


def solve():
	T = int(input())
	for t in range(T):
		no_boxes = int(input())
		boxes = [int(temp) * 7 for temp in input().split()]
		no_bands = int(input())
		rubber_bands = []
		for b in range(no_bands):
			(R1, R2) = input().split()
			rubber_bands.append([int(R2) * 11, int(R1) * 11])
		boxes.sort()
		rubber_bands.sort()
		i = j = ans = 0
		for box in boxes:
			j = 0
			for band in rubber_bands:
				low = band[1]
				high = band[0]
				if box >= low and box <= high:
					ans += 1
					del rubber_bands[j]
					break
				j += 1
		print(ans)
solve()