Connection Status:
Competition Arena > IntervalSubsets

IntervalSubsets

SRM 387 · 2008-01-09 · by Relja

SRM 387 · 2008-01-09 · by Relja · Dynamic Programming
Class Name: IntervalSubsets
Return Type: int
Method Name: numberOfSubsets
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

You are given two int[]s, start and finish, representing a set of intervals. The i-th interval is between start[i] and finish[i], inclusive. A subset of the given set is valid only if the following two conditions are satisfied:

  1. No two intervals in the subset intersect each other. Two intervals intersect each other if they both contain at least one common number.
  2. Adding any remaining interval from the original set would make the subset invalid.

Return the number of distinct valid subsets of the given set. Two subsets are distinct if there is at least one interval in the first subset which is not in the second. Two intervals are distinct if their indexes in start (so, in finish also) are different. Correct result will always fit in 32-bit signed integer.

Constraints

  • start and finish will each contain between 1 and 50 elements, inclusive.
  • start and finish will contain the same number of elements.
  • For all i, start[i] will be less than or equal to finish[i].
  • Each element of start and finish will be between 1 and 100, inclusive.
Examples
0)
{3}
{4}
Returns: 1
1)
{68,25}
{75,64}
Returns: 1

The whole set is the only valid subset.

2)
{4,2,3}
{4,5,3}
Returns: 2

The given set of intervals is {[4, 4], [2, 5], [3, 3]}. The valid subsets are {[4, 4], [3, 3]} and {[2, 5]}.

3)
{36,74,8,33}
{63,91,57,51}
Returns: 3
4)
{3,4,3,2,1}
{4,5,4,5,5}
Returns: 5
67)
{1, 1, 3, 3}
{2, 2, 4, 4}
Returns: 4

The given set of intervals is {[1, 2], [1, 2], [3, 4], [3, 4]}. We can combine each of the first two intervals with each of the other two.

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

Coding Area

Language: C++17 · define a public class IntervalSubsets with a public method int numberOfSubsets(vector<int> start, vector<int> finish) · 85 test cases · 2 s / 256 MB per case

Submitting as anonymous