12

私は次のものを持っています：

public class Interval
{
   DateTime Start;
   DateTime End; 
}

List<Interval>複数の間隔を含むオブジェクトがあります。私は次のことを達成しようとしています（理解しやすいように数字を使用しました）：

[(1, 5), (2, 4), (3, 6)] --->  [(1,6)]
[(1, 3), (2, 4), (5, 8)] --->  [(1, 4), (5,8)]

私は現在、次のように Python でこれを行っています。

def merge(times):
    saved = list(times[0])
    for st, en in sorted([sorted(t) for t in times]):
        if st <= saved[1]:
            saved[1] = max(saved[1], en)
        else:
            yield tuple(saved)
            saved[0] = st
            saved[1] = en
    yield tuple(saved)

しかし、C＃で同じことを達成しようとしています（LINQが最適ですがオプションです）。これを効率的に行う方法について何か提案はありますか?

4

5 に答える 5

14

これが使用しているバージョンです-まだ遅延評価されていますが、クエリを実行yield returnするよりも読みやすいと思います。Aggregateこれは、リストをすでに注文していることを前提としています。そうでない場合は、そのステップを追加するだけです。

IEnumerable<Interval> MergeOverlappingIntervals(IEnumerable<Interval> intervals)
{
  var accumulator = intervals.First();  
  intervals = intervals.Skip(1);

  foreach(var interval in intervals)
  {
    if ( interval.Start <= accumulator.End )
    {
        accumulator = Combine(accumulator, interval);
    }
    else
    {
        yield return accumulator;
        accumulator = interval;     
    }       
  }

  yield return accumulator;
}

Interval  Combine(Interval start, Interval end)
{
  return new Interval 
  {
    Start = start.Start,
    End = Max(start.End, end.End),
  };
}

private static DateTime Max(DateTime left, DateTime right) 
{
    return (left > right) ? left : right;
}
于 2012-07-14T02:03:23.010 に答える
3

これは最も美しい解決策ではないかもしれませんが、うまくいくかもしれません

public static List<Interval> Merge(List<Interval> intervals)
{
    var mergedIntervals = new List<Interval>();
    var orderedIntervals = intervals.OrderBy<Interval, DateTime>(x => x.Start).ToList<Interval>();

    DateTime start = orderedIntervals.First().Start;
    DateTime end = orderedIntervals.First().End;

    Interval currentInterval;
    for (int i = 1; i < orderedIntervals.Count; i++)
    {
        currentInterval = orderedIntervals[i];

        if (currentInterval.Start < end)
        {
            end = currentInterval.End;
        }
        else
        {
            mergedIntervals.Add(new Interval()
            {
                Start = start,
                End = end
            });

            start = currentInterval.Start;
            end = currentInterval.End;
        }
    }

    mergedIntervals.Add(new Interval()
                {
                    Start = start,
                    End = end
                });

    return mergedIntervals;
}

フィードバックをいただければ幸いです。

よろしく

于 2012-07-14T01:24:45.823 に答える
1

この種のマージは、通常、関数型言語の折り畳みと見なされます。LINQ に相当するものはAggregate.

IEnumerable<Interval<T>> Merge<T>(IEnumerable<Interval<T>> intervals) 
  where T : IComparable<T>
{
    //error check parameters
    var ret = new List<Interval<T>>(intervals);
    int lastCount
    do
    {
        lastCount = ret.Count;
        ret = ret.Aggregate(new List<Interval<T>>(),
                    (agg, cur) =>
                    {
                        for (int i = 0; i < agg.Count; i++)
                        {
                            var a = agg[i];
                            if (a.Contains(cur.Start))
                            {
                                if (a.End.CompareTo(cur.End) <= 0)
                                {
                                    agg[i] = new Interval<T>(a.Start, cur.End);
                                }
                                return agg;
                            }
                            else if (a.Contains(cur.End))
                            {
                                if (a.Start.CompareTo(cur.Start) >= 0)
                                {
                                    agg[i] = new Interval<T>(cur.Start, a.End);
                                }
                                return agg;
                            }
                        }
                        agg.Add(cur);
                        return agg;
                    });
    } while (ret.Count != lastCount);
    return ret;
}

Interval クラスをジェネリック ( Interval<T> where T : IComparable<T>) にして、メソッドを追加し、bool Contains(T value)不変にしましたが、現在のクラス定義をそのまま使用する場合は、あまり変更する必要はありません。

于 2012-07-14T01:53:43.617 に答える