Inequalities | Topcoder Archive

Problem Statement

You're given a set of inequalities. Each of the inequalities refers to the variable X. Determine the maximum subset of the given set which has a solution.

To make your task easier, the inequalities in the given set are always reduced to one of the following five forms:

	X &lt; C
	X &lt;= C
	X = C
	X &gt; C
	X &gt;= C

Here, C indicates some non-negative integer constant.

The inequalities are given in the String[] inequalities, where each element is a single inequality formatted as shown above. Return the maximal number of inequalities of the set which can be satisfied simultaneously.

Definition

Class:: Inequalities
Method:: maximumSubset
Parameters:: String[]
Returns:: int
Method signature:: int maximumSubset(String[] inequalities)
(be sure your method is public)

Notes

Note that X doesn't have to be an integer or positive number.

Constraints

inequalities will contain between 1 and 50 elements, inclusive.
Each element of inequalities will be formatted "X <E> <C>", where 'X' is uppercase, <E> is one of "<", "<=", "=", ">=" or ">", and <C> is an integer between 0 and 1000, inclusive, with no extra leading zeroes (all quotes for clarity).
No two elements of inequalities will be equal.

Examples

```
{"X <= 12","X = 13","X > 9","X < 10","X >= 14"}
```
```
Returns: 3
```
Any value between 9 and 10 will satisfy the first, third and fourth inequalities.
```
{"X < 0","X <= 0"}
```
```
Returns: 2
```
The solution to the whole set is any negative number.
```
{"X = 1","X = 2","X = 3","X > 0"}
```
```
Returns: 2
```
Obviously, you can choose no more than one equality in addition to the fourth inequality.

{"X <= 521","X >= 521","X = 521","X > 902","X > 12","X <= 1000"}

Returns: 5

The best choice is number 521.

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)2024, Topcoder, Inc. All rights reserved.