PROBLEM STATEMENT
You are given a set of integers called luckySet. An interval [A,B], where B is greater than A,
and A and B are positive integers, is considered unlucky if none of the integers between A and B,
inclusive, belongs to luckySet.
An integer x is considered to be luckier than another integer y if the number of unlucky intervals
that contain x is smaller than the number of unlucky intervals that contain y. In case both x and
y belong to an equal number of unlucky intervals, or both belong to an infinite number of unlucky
intervals, the smallest of them is considered to be luckier than the other.
Given a vector luckySet, return the top n luckiest positive integers sorted in descending
order by luckiness (in other words, each element of the vector must be luckier than the next
element).
DEFINITION
Class:UnluckyIntervals
Method:getLuckiest
Parameters:vector , int
Returns:vector
Method signature:vector getLuckiest(vector luckySet, int n)
CONSTRAINTS
-luckySet will contain between 1 and 50 elements, inclusive.
-Each element of luckySet will be between 1 and 1000000000, inclusive.
-Each element of luckySet will be distinct.
-n will be between 1 and 100, inclusive.
EXAMPLES
0)
{3}
6
Returns: {3, 1, 2, 4, 5, 6 }
0 unlucky intervals contain 3.
1 unlucky interval contains 1: [1,2].
1 unlucky interval contains 2: [1, 2].
Since 1 and 2 are inside an equal number of intervals, 1 is considered luckier because it is less
than 2.
For every number greater than 3, there is an infinite number of unlucky intervals that contain it.
However, 4 and 5 are considered to be the luckiest among them, as they are smallest.
1)
{5, 11, 18}
9
Returns: {5, 11, 18, 1, 4, 6, 10, 2, 3 }
3 unlucky intervals: [1,2], [1,3] and [1,4] include 1.
3 unlucky intervals: [1,4], [2,4] and [3,4] include 4.
4 unlucky intervals: [6,7], [6,8], [6,9] and [6,10] include 6.
4 unlucky intervals: [6,10], [7,10], [8,10] and [9,10] include 10.
5 unlucky intervals: [1,2], [1,3], [1,4], [2,3] and [2,4] include 2.
5 unlucky intervals: [1,3], [1,4], [2,3], [2,4] and [3,4] include 3.
2)
{7, 13, 18}
9
Returns: {7, 13, 18, 14, 17, 8, 12, 1, 6 }
3)
{1000, 1004, 4000, 4003, 5000}
19
Returns: {1000, 1004, 4000, 4003, 5000, 4001, 4002, 1001, 1003, 1002, 4004, 4999, 1, 999, 4005,
4998, 2, 998, 4006 }
4)
{1000000000}
8
Returns: {1000000000, 1, 999999999, 2, 999999998, 3, 999999997, 4 }
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.