CODEWITHSUNDEEP
c#arrayslinqsubset
Kunal Mukherjee
Kunal Mukherjee

Reputation: 5853

How to return all ranges that are not included in any other range C# list

I have a List of value Tuple as follows:

List<(int, int)> values = new List<(int, int)>
{
  (12, 15),
  (18, 30),
  (18, 27),
  (27, 30)
};

Now I want to remove the pairs in this list, which is inside the range of the wider pair.

For example: (18, 27) and (27, 30) are in the range of (18, 30). So, I want to remove those pairs which lie under it.

So the final output must be:

(12, 15)
(18, 30)

I was thinking of removing those pairs using the .RemoveAll() method of LINQ but I am stuck as how to do so.

Any help will be appreciated.

Upvotes: 0

Views: 309

Answers (2)

MineR
MineR

Reputation: 2204

I believe this should work and should be n*log(n):

//You will see some Math.Max and Math.Min - these are required because in your comments 
//you state the pairs can be out of order (the second value is less than the first)

int upper = int.MinValue;
values = values
    //Group all pairs by their minimum value, so (18,30) and (18,27) for example 
    //would be processed together
    .GroupBy(x => Math.Min(x.Item1, x.Item2))
    //Sort the groups based on their minimum value, so they can be processed in order. 
    //Although your example does not require this, the comments say this is required.
    .OrderBy(x => x.Key)
    //From the group [which may contain (18,30) and (18,27) for example],
    //only choose the one with the highest max value. This will choose (18,30)
    .Select(x => x.OrderBy(y => Math.Max(y.Item1, y.Item2)).Last())
    //Now iterate through the items and throw away the items which are inside
    //a pair previously processed pair. We use the upper variable to
    //keep track of the greatest processed upper bound to make throwing away 
    //previously processed pairs easy
    .Where(x =>
    {
        var max = Math.Max(x.Item1, x.Item2);
        if (upper < max)
        {
            upper = max;
            return true;
        }
        else
        {
            return false;
        }

    }).ToList();

This can certainly be made faster without Linq, depending on how important memory and performance are for your application.

Upvotes: 1

NotFound
NotFound

Reputation: 6192

If I understood correctly this will do the trick. It compares each value of the list with the entire list till it finds another tuple where it falls within the range that's not exactly equal.

List<(int, int)> values = new List<(int, int)>
{
    (12, 15),
    (18, 30),
    (18, 27),
    (27, 30)
};

values.RemoveAll(x => values.Any(y => x.CompareTo(y) != 0 && x.Item1 >= y.Item1 && x.Item2 <= y.Item2));

Upvotes: 2

Related Questions