UnluckyIntervals

SRM 438 · 2009-04-18 · by vexorian

SRM 438 · 2009-04-18 · by vexorian · Greedy, Search

Show categories

Class Name: UnluckyIntervals

Return Type: int[]

Method Name: getLuckiest

Arg Types: (vector<int>, int)

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 int[] luckySet, return the top n luckiest positive integers sorted in descending order by luckiness (in other words, each element of the int[] must be luckier than the next element).

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

{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.

{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.

{7, 13, 18}
9
Returns: {7, 13, 18, 14, 17, 8, 12, 1, 6 }

{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 }

{2}
1
Returns: {1 }

24)

{499999999,1000000000}
100
Returns: {499999999, 1000000000, 1, 499999998, 500000000, 999999999, 2, 499999997, 500000001, 999999998, 3, 499999996, 500000002, 999999997, 4, 499999995, 500000003, 999999996, 5, 499999994, 500000004, 999999995, 6, 499999993, 500000005, 999999994, 7, 499999992, 500000006, 999999993, 8, 499999991, 500000007, 999999992, 9, 499999990, 500000008, 999999991, 10, 499999989, 500000009, 999999990, 11, 499999988, 500000010, 999999989, 12, 499999987, 500000011, 999999988, 13, 499999986, 500000012, 999999987, 14, 499999985, 500000013, 999999986, 15, 499999984, 500000014, 999999985, 16, 499999983, 500000015, 999999984, 17, 499999982, 500000016, 999999983, 18, 499999981, 500000017, 999999982, 19, 499999980, 500000018, 999999981, 20, 499999979, 500000019, 999999980, 21, 499999978, 500000020, 999999979, 22, 499999977, 500000021, 999999978, 23, 499999976, 500000022, 999999977, 24, 499999975, 500000023, 999999976, 25, 499999974 }

This case is overflow-friendly.

Submissions are judged against all 153 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class UnluckyIntervals with a public method vector<int> getLuckiest(vector<int> luckySet, int n) · 153 test cases · 2 s / 256 MB per case