Как вернуть все диапазоны, которые не включены ни в один другой список C # диапазонов - PullRequest
Новая
       9

Как вернуть все диапазоны, которые не включены ни в один другой список C # диапазонов

0 голосов
/ 05 июля 2018

У меня есть список значений Tuple следующим образом: 

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

Теперь я хочу удалить пары из этого списка, который находится внутри диапазона более широкой пары.

Например: (18, 27) и (27, 30) находятся в диапазоне (18, 30). Итак, я хочу удалить те пары, которые лежат под ним.

Таким образом, конечный результат должен быть: 

(12, 15)
(18, 30)

Я думал об удалении этих пар с помощью метода .RemoveAll() LINQ, но я застрял, как это сделать.

Любая помощь будет оценена.

Ответы [ 2 ]

0 голосов
/ 05 июля 2018

Я считаю, что это должно работать и должно быть 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();

Без Linq это можно сделать быстрее, в зависимости от того, насколько важны память и производительность для вашего приложения.

0 голосов
/ 05 июля 2018

Если я правильно понял, это сработает. Он сравнивает каждое значение списка со всем списком, пока не найдет другой кортеж, где он попадает в диапазон, который не совсем равен. 

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));
...