You approach is invalid, because when Rule1 intersects with Rule2 and Rule1 intersects with Rule3 this doesn't mean that Rule2 intersects with Rule3.
Example:
Rule1: [1,2] [3,4] [5,6]
Rule2: [1,1] [3,3] [5,5]
Rule3: [2,2] [4,4] [6,6]
In your solution when you fix Rule1 in outer loop then find Rule2 and Rule3 in nested loop and get the result of 3, while correct answer is 2.
I have a working solution in mind, but it's not very efficient: O(K3 * N) where K comes from the domain of definition of rules' intervals (K = max_interval_value - min_interval_value) and N is the number of rules. Also it consumes O(K * N) memory. If this setup fits problem's time and memory limits, I can describe my solution, if not, I'll rather will not waste my time.
Update:
Ok, here we go. For simplicity I will assume that minimum number that appears in rules is 0 and the maximum is K. So there are only K+1 possible integer numbers that can satisfy at least one rules' interval.
As each rule has exactly three intervals, you have to create three arrays that will correspond to these intervals. Array's element at index i will contain the set of rules that include number i in their corresponding interval. Each array has length of K+1.
For example, if we have rules:
A: [1,2][3,4][5,6]
B: [1,1][2,2][6,6]
C: [2,2][4,4][5,5]
Then first array (that corresponds to intervals at position 1) will be:
0:{}, 1:{A,B}, 2:{A,C}, 3:{}.... rest are empty sets
Second array corresponds to intervals at second position:
0:{}, 1:{}, 2:{B}, 3:{A}, 4:{A, C}, 5:{}, 6:{}
Third array will be:
...all empty... 5: {A, C}, 6: {A, B}
Now how to fill these arrays. You start with empty sets in each element. Then you go through all rules. For each rule you iterate through all values that lie in corresponding interval and add current rule into appropriate set. For example, for rule A for first interval you need to iterate through values 1,2 and add A into first array at indexes 1,2. This part takes 3 * K * N steps (assuming adding element to set is O(1))
What you do next is basically trying to figure an input that will satisfy most rules. You need three nested loops, say, i for first interval, j for second interval, k for third. You need to iterate through all possible values from 0 to K. And for each combination of i,j,k you need to intersect three sets, each taken from corresponding array. So, returning to the example, for i=2, j=4, k=5 you will need to intersect {A, C} with {A, C} with {A, C}, and this will result actually largest set of rules. For i=1, j=3, k=5 you will intersect {A,B} with {A} and {A,C} and get only {A}. So, you iterate, calculating intersection and finding maximal set of rules. The complexity of this part is O( K3 * N) where K3 comes from nested loops and N is the cost of set intersection.
That's all. I haven't thought much on this solution, so maybe it can be further optimized. But at least it is polynomial.
Update
Now how to eliminate one nested loop.
When you have some i and j and already computed intersection of groups from first two arrays, you get virtually new task. Now you have set of groups and you need to find maximal subset of this set that will satisfy only one remained interval (third). What I propose is to iterate all possible values from 0 to K and for each value maintain the set of groups that are satisfied by that value. In order to do that you have to sort initial subset of groups in two ways, first by first interval's boundary, second by second interval's boundary. Lets call first sorted array add_order, second remove_order. (Later you see that these arrays can be replaced by queues for simplicity).
If you have three groups in you initial subset:
A: [..][..][2,4]
B: [..][..][2,2]
C: [..][..][1,3]
They will be ordered as this: C, A, B for add_order.
C: [..][..][1,3]
A: [..][..][2,4]
B: [..][..][2,2]
And B, C, A for remove_order:
B: [..][..][2,2]
C: [..][..][1,3]
A: [..][..][2,4]
You need three pointers in your loop. First (g_add) will point (in array add_order) at the group you are about to "add" to your maintained set, second (g_remove) will point (in array remove_order) at the group you are about to remove from your set. And the last, k will hold current value (from 0 to K).
Returning to example, you will iterate k from 0 to 5 (g_add and g_remove initially pointing on first group of corresponding array):
k=0, g_add=C, g_remove=B, res={} // nothing to do
k=1, g_add=C, g_remove=B, res={} // `g_add` is pointing on the group whose first boundary is less or equal to `k`, adding this group to set of current groups, and incrementing `g_add`
k=1, g_add=A, g_remove=B, res={C} // moving on, incrementing `k`
k=2, g_add=A, g_remove=B, res={C} // now A satisfies adding condition
k=2, g_add=B, g_remove=B, res={C, A} // B satisfies adding condition too
k=2, g_add=, g_remove=B, res={C, A, B} // incrementing k (note that at that point we have largest set)
k=3, g_add=, g_remove=B, res={C, A, B} // B has second boundary less than k, removing
k=3, g_add=, g_remove=C, res={C, A} // B has second boundary less than k, removing
k=3, g_add=, g_remove=C, res={C, A} // k++
k=4, g_add=, g_remove=C, res={C, A} // C is suitable for removing
k=4, g_add=, g_remove=A, res={A} // k++
k=5, g_add=, g_remove=A, res={A} // A is suitable for removing
k=5, g_add=, g_remove=, res={} // we are done
As I said before, you can consider remove_order and add_order as a queues and their heads will be add and remove candidates correspondingly.
Now about complexity. Iterate all pairs of i and j takes O(K2). Now for each such pair you do sets intersection O(N), you don't need to sort the groups, as this can be done at very beginning, before the loops. Then you need to iterate k, adding and removing groups. As each group is processed only twice (when adding and removing) and k is iterated from 0 to K the complexity of this loop will be O(N + K).
So for the whole algorithm we get O(K2 * (N + K)) that, considering K << N roughly will be O(K2 * N).
