kth smallest number again

Solutions on MaxInterview for kth smallest number again by the best coders in the world

showing results for - "kth smallest number again"
Antonio
03 Aug 2016
1
2void solve() {
3
4	int n, q;
5	cin >> n >> q;
6	// v =  [{1, 7}, {10, 15}]
7	vector<pair<int, int>> arr(n);
8	for (int i = 0; i < n; i++) {
9		cin >> arr[i].ff >> arr[i].ss;
10	}
11
12	// v =  [{10, 15}, {1, 7}]
13
14	sort(arr.begin(), arr.end());
15
16	// v = [{1, 7}, {10, 15}];
17
18	// case : v = [{1, 7}, {15, 10}];
19	int idx = 0;
20	for (int i = 1; i < n; i++) {
21		if (arr[idx].ff > arr[idx].ss) {
22			arr[idx].ss = max(arr[idx].ff, arr[idx].ss);
23		}
24		else {
25			idx++;
26			arr[idx] = arr[i];
27		}
28	}
29
30	// Searching
31	while (q--) {
32
33		int k;
34		cin >> k;
35
36		int ans = -1;
37		for (int i = 0; i <= idx; i++) {
38			if (arr[i].ss - arr[i].ff + 1 > k) {
39				ans = arr[i].ff + k - 1;
40				break;
41			}
42			else {
43				k -= arr[i].ss - arr[i].ff + 1;
44			}
45		}
46		cout << ans << '\n';
47	}
48
49
50
51}
52