I have a question about a matrix.
There is a matrix and a list of segments. Every segment has a name, a start or end point and a value that descrips if the start and end point refers to rows or colums of the matrix.
There can be more than one segments with the same name (but with differet start and end points).
Now we have a list of names (a , b , c).
The task is to find every matrix position (x,y) where the position fits into the range (start and end point) of every segment with a name of the list.
What is the fastes way to do this?
I need this to finde the position of a logic expression in a KV-Diagram.
If the intervals with the same name are not overlapping then it is pretty easy to come up with an algorithm with complexity O(r * c * n). r = #rows, c = #columns and n = #names.
Initialize an r*c count matrix with 0s.
For each name...
For each interval with name ...
Increase all values of the count matrix which are inside the interval by 1.
Iterate over the count matrix and return all the cells where count == n.
If the intervals with the same name are not overlapping then you have to increase at most r * c values per name n, so the complexity is O(r * c * n), the + r * c in the last step don't matter.