C# Найти все отсутствующие сегменты во времени

Question

Мне нужно найти недостающие сегменты в течение 10 минут, и мне интересно, какой лучший маршрут займет.

Допустим, у меня есть три сегмента во времени.

1. 2:30 - 3:43 минутный сегмент.
2. 4:25 - 4:59 минутный сегмент.
3. 7:21 - 9:55 минутный сегмент.

С C# у меня есть полный 10-20 минутный сегмент времени. Мне нужно найти недостающие сегменты, когда у меня уже есть 3 сегмента сверху.

Так сегменты мне нужно вычислить с C# являются следующими

1. 0:00 - 2:29 минут сегмента.
2. 3:44 - 4:24 минутный сегмент.
3. 5:00 - 7:20 минутный сегмент.
4. 9:56 - 10:20 минутный сегмент.

Итак, я рассчитываю эти 4 сегмента из 3 сегментов, которые я уже знаю выше?

Я думаю, что мой лучший маршрут состоит в том, чтобы просто сделать цикл цикла и подсчитать до 10:20 в секундах и проверить, существует ли эта вторая секунда в трех сегментах. Если нет, добавьте эту секунду к отсутствующему сегменту.

Answer 1

Не думаю, что это хорошая идея проверить каждую секунду, если она принадлежит интервалу. Я думаю, что эту проблему можно решить, имея O(n) complexity, конечно, используя некоторые .NET-классы для структурирования ввода, который сделает все более легким. Полная скрипка here.

private static List<Tuple<TimeSpan,TimeSpan>> ComputeMissingTimeSpans(List<Tuple<TimeSpan,TimeSpan>> availableIntervals, TimeSpan minSpan, TimeSpan maxSpan) 
    { 
     List<Tuple<TimeSpan,TimeSpan>> missingTime = new List<Tuple<TimeSpan,TimeSpan>>(); 
     if(availableIntervals.Count == 0) 
     { 
      missingTime.Add(new Tuple<TimeSpan, TimeSpan>(minSpan, maxSpan)); 
      return missingTime; 
     } 

     foreach(var interval in availableIntervals){ 
      if((interval.Item1 - minSpan).TotalSeconds > 1) 
      { 
       missingTime.Add(new Tuple<TimeSpan, TimeSpan>(minSpan, interval.Item1.Add(TimeSpan.FromSeconds(-1)))); 
      } 

      minSpan = interval.Item2.Add(TimeSpan.FromSeconds(1)); 
     } 

     if((maxSpan - minSpan).TotalSeconds > 1) 
      missingTime.Add(new Tuple<TimeSpan, TimeSpan>(minSpan, maxSpan)); 

     return missingTime; 
    } 

Вы можете легко адаптировать эту функцию к вашим потребностям.

Answer 2

После яркой идеей Джонсон @ Matt, а также для более общего решения также подходит для длинных и/или периодов, можно создать TimeSlot-структуру:

public struct TimeSlot 
{ 
    private DateTime _start; 
    private TimeSpan _span; 

    public DateTime Start 
    { 
     get 
     { 
      if (_start == null) 
      { 
       _start = DateTime.Today; 
      } 
      return _start; 
     } 

     set 
     { 
      _start = value; 
     } 
    } 

    public TimeSpan Span 
    { 
     get 
     { 
      if (_span == null) 
      { 
       _span = new TimeSpan(0); 
      } 
      return _span; 
     } 

     set 
     { 
      if (value.Ticks >= 0) 
      { 
       _span = value; 
      } 
     } 
    } 

    public DateTime End 
    { 
     get 
     { 
      return Start.Add(Span); 
     } 
    } 

    public TimeSlot(DateTime start, TimeSpan span) 
    { 
     _start = start; 
     _span = span.Ticks >= 0 ? span : new TimeSpan(0); 
    } 
} 

Затем вы можете запустить код, как это, где вы сначала найти ведущий сегмент, то эти сегменты между ними, и, наконец, сегментом косой:

public static void SlotDemo() 
{ 
    DateTime startTime = DateTime.Today; 
    DateTime endTime = startTime.Add(new TimeSpan(0, 10, 20)); 

    List<TimeSlot> segments = new List<TimeSlot>(); 
    segments.Add(new TimeSlot(startTime.Add(new TimeSpan(0, 2, 30)), new TimeSpan(0, 1, 13))); 
    segments.Add(new TimeSlot(startTime.Add(new TimeSpan(0, 4, 25)), new TimeSpan(0, 0, 35))); 
    segments.Add(new TimeSlot(startTime.Add(new TimeSpan(0, 7, 21)), new TimeSpan(0, 2, 34))); 

    for (int i = 0; i < segments.Count; i++) 
    { 
     Console.WriteLine("s: {0:mm':'ss} d: {1:mm':'ss} e: {2:mm':'ss}", segments[i].Start, segments[i].Span, segments[i].End); 
    } 
    Console.WriteLine(); 

    if (!segments[0].Start.Equals(startTime)) 
    { 
     TimeSlot firstSlot = new TimeSlot(startTime, segments[0].Start.Subtract(startTime)); 
     segments.Insert(0, firstSlot); 
    } 

    for (int i = 0; i < segments.Count; i++) 
    { 
     Console.WriteLine("s: {0:mm':'ss} d: {1:mm':'ss} e: {2:mm':'ss}", segments[i].Start, segments[i].Span, segments[i].End); 
    } 
    Console.WriteLine(); 

    for (int i = 0; i < segments.Count - 1; i++) 
    { 
     if (segments[i].End != segments[i + 1].Start) 
     { 
      TimeSlot slot = new TimeSlot(segments[i].End, segments[i + 1].Start.Subtract(segments[i].End)); 
      segments.Insert(i + 1, slot); 
      i++; 
     } 
    } 

    for (int i = 0; i < segments.Count; i++) 
    { 
     Console.WriteLine("s: {0:mm':'ss} d: {1:mm':'ss} e: {2:mm':'ss}", segments[i].Start, segments[i].Span, segments[i].End); 
    } 
    Console.WriteLine(); 

    int lastIndex = segments.Count - 1; 
    if (!segments[lastIndex].End.Equals(endTime)) 
    { 
     TimeSlot lastSlot = new TimeSlot(segments[lastIndex].End, endTime.Subtract(segments[lastIndex].End)); 
     segments.Add(lastSlot); 
    } 

    for (int i = 0; i < segments.Count; i++) 
    { 
     Console.WriteLine("s: {0:mm':'ss} d: {1:mm':'ss} e: {2:mm':'ss}", segments[i].Start, segments[i].Span, segments[i].End); 
    } 
    Console.ReadKey(); 
} 

, который обеспечит этот вывод:

s: 02:30 d: 01:13 e: 03:43 
s: 04:25 d: 00:35 e: 05:00 
s: 07:21 d: 02:34 e: 09:55 

s: 00:00 d: 02:30 e: 02:30 
s: 02:30 d: 01:13 e: 03:43 
s: 04:25 d: 00:35 e: 05:00 
s: 07:21 d: 02:34 e: 09:55 

s: 00:00 d: 02:30 e: 02:30 
s: 02:30 d: 01:13 e: 03:43 
s: 03:43 d: 00:42 e: 04:25 
s: 04:25 d: 00:35 e: 05:00 
s: 05:00 d: 02:21 e: 07:21 
s: 07:21 d: 02:34 e: 09:55 

s: 00:00 d: 02:30 e: 02:30 
s: 02:30 d: 01:13 e: 03:43 
s: 03:43 d: 00:42 e: 04:25 
s: 04:25 d: 00:35 e: 05:00 
s: 05:00 d: 02:21 e: 07:21 
s: 07:21 d: 02:34 e: 09:55 
s: 09:55 d: 00:25 e: 10:20