Вычислить пересечение/перехват между двумя списками, которые содержат диапазоны

Question

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

Класс, представляющий диапазоны ниже, будет содержать два свойства, время начала и время окончания, которое может быть датой или временем. Каждая команда может иметь список из них. Срок службы недвижимости снижается до минуты, так что действует 14:21.

Команда 1 не может играть между этими двумя перечнями, поэтому они могут играть только с 10:00 AM до 5:00. Однако мы сохраняем исключение.

Команда 2 может сыграть 8:00 AN-12: 00 PM.

Значение Команда 1 и команда 2 могут играть между 10-12. Есть ли хороший способ рассчитать это в коде?

Команда 1

List<Restriction> 
    Restriction 
      StartTime: 8:00 AM 
      EndTime: 10:00 AM 
    Restriction 
      StartTime: 5:00 PM 
      EndTime: 9:00 PM 

Команда 2

List<Restriction> 
    Restriction 
      StartTime: 12:00 PM 
      EndTime: 9:00 PM 

Answer 1

Сделать массив всех начальных и конечных времен, включая +1 или -1, в зависимости от того, является ли каждый раз началом или временем окончания.

Для вашего множество раз, это дает:

[(08:00, +1), (10:00, -1), (17:00, +1), (21:00, -1), (12:00, +1), (21:00, -1)] 

Сортировать им:

[(08:00, +1), (10:00, -1), (12:00, +1), (17:00, +1), (21:00, -1), (21:00, -1)] 

Do бегущую сумму плюс и минус 1-х:

[(08:00, 1), (10:00, 0), (12:00, 1), (17:00, 2), (21:00, 1), (21:00, 0)] 

В Текущая сумма - это количество команд (0, 1 или 2), которые заняты, начиная с этого времени. Таким образом, время, которое теперь обозначается 0, является временем начала, когда обе команды свободны (здесь 10:00 и 21:00). В следующий раз в массиве будет конец свободного периода. Это дает временные периоды, когда обе команды свободны, в том числе в начале и в конце (-инфекция до 08:00), (с 10:00 до 12:00) и (с 21:00 до + бесконечность).

Answer 2

После может помочь, вы говорите о временном диапазоне и, когда команда может играть, также пересечения с другой командой. В настоящее время, как я вижу из примера, минимальная единица составляет 1 час, говорят 8-9, 9-10. Общее время, похоже, находится между 8:00 до 21:00, это может быть что угодно. Если мое понимание верное.

Теперь сформируйте диапазоны минимальной единицы как 8-9, 9-10, 10-11 и используйте в структуре данных, как словарь, чтобы обновить логическое значение true/false, может ли команда играть или нет, теперь вам нужно выбрать все диапазоны, где оба являются истинными, и которые будут пересечением или диапазонами воспроизведения.

Структура данных может быть - Dictionary<Tuple<int,int>, bool>

я не знаю дальнейшей сложности, но вы можете использовать подобную логику, чтобы включать в себя дни недели, месяц и год тоже.

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

Answer 3

Вот рабочая версия кода, на основе предоставленных данных в вопросе, важные детали:

1. Временной интервал зернистость в течение нескольких минут, это может быть даже в секундах.
2. Он печатает окончательный ответ в 24-часовом формате.
3. Время начинается с 0 часов - 24 часа, поэтому он отображает часы игры как 0-8, 10-12 и 21-24. Требуется дополнительная логика для удаления часов, таких как 0-8, 21-24, если они определены как необычные часы
4. Код не соответствует всем стандартам кодирования, он просто заботится о ожидаемой логике и алгоритме, предложенном в последний ответ.

5. Пожалуйста, дайте знать, в случае, если вам нужны разъяснения, связанные с реализацией

   using System; 
   using System.Collections.Generic; 
   
   public class PlayTimeTest 
   { 
   public static void Main(string[] args) 
   { 
       IntersectTime teamIntersectingTime = new IntersectTime(); 
       teamIntersectingTime.CreateTeams(); 
   
       Dictionary<Tuple<int, int>, bool> validTimeSlot = teamIntersectingTime.FindTimeSlot(); 
   
       teamIntersectingTime.PlayTimeDisplay(validTimeSlot); 
       Console.ReadLine(); 
   } 
   } 
   
   
   internal class IntersectTime 
   { 
       Team teamA { get; set; } 
       Team teamB { get; set; } 
   
   public void CreateTeams() 
   { 
       TimeRestriction A1 = new TimeRestriction(); 
       A1.startTime = 8; 
       A1.endTime = 10; 
   
       TimeRestriction A2 = new TimeRestriction(); 
       A2.startTime = 17; 
       A2.endTime = 21; 
   
       List<TimeRestriction> teamARestrictions = new List<TimeRestriction>(); 
       teamARestrictions.Add(A1); 
       teamARestrictions.Add(A2); 
   
       teamA = new Team(teamARestrictions); 
       teamA.CreateSlotDictionary(); 
   
       TimeRestriction B1 = new TimeRestriction(); 
       B1.startTime = 12; 
       B1.endTime = 21; 
   
   
       List<TimeRestriction> teamBRestrictions = new List<TimeRestriction>(); 
       teamBRestrictions.Add(B1);   
   
       teamB = new Team(teamBRestrictions); 
       teamB.CreateSlotDictionary(); 
   } 
   
   public Dictionary<Tuple<int,int>,bool> FindTimeSlot() 
   { 
       Dictionary<Tuple<int, int>, bool> returnTimeSlot = new Dictionary<Tuple<int, int>, bool>(); 
   
       foreach(KeyValuePair<Tuple<int, int>, bool> currentIndividualSlot in teamA.AvailableSlot) 
       { 
        if (currentIndividualSlot.Value == true && teamB.AvailableSlot[currentIndividualSlot.Key] == true) 
         returnTimeSlot.Add(currentIndividualSlot.Key, currentIndividualSlot.Value); 
       } 
   
       return (returnTimeSlot); 
   } 
   
   public void PlayTimeDisplay(Dictionary<Tuple<int, int>, bool> validTimeSlot) 
   { 
       int startValidTime = 0; 
   
       int endValidTime = 0; 
   
       int testCounter = 0; 
   
       KeyValuePair<Tuple<int, int>, bool> playBeginTime = new KeyValuePair<Tuple<int, int>, bool>(); 
       KeyValuePair<Tuple<int, int>, bool> lastPlayTime = new KeyValuePair<Tuple<int, int>, bool>(); 
   
       foreach(KeyValuePair<Tuple<int, int>, bool> playTime in validTimeSlot) 
       { 
        lastPlayTime = playTime; 
        startValidTime = playTime.Key.Item1; 
   
        if(testCounter == 0) 
         playBeginTime = playTime; 
   
        if(endValidTime !=0 && (startValidTime != endValidTime)) 
        { 
         int beginTimeInMinutes = playBeginTime.Key.Item1; 
         int endTimeInMinutes = endValidTime; 
   
         int timeResult; 
   
         int beginTimeInHours = Math.DivRem(beginTimeInMinutes, 60, out timeResult); 
         int endTimeInHours = Math.DivRem(endTimeInMinutes, 60, out timeResult); 
   
         Console.WriteLine("Teams play between :: " + beginTimeInHours + " - " + endTimeInHours + "hours"); 
         testCounter = 0; 
         endValidTime = playTime.Key.Item2; 
        } 
        else 
        { 
         endValidTime = playTime.Key.Item2; 
         testCounter ++; 
        } 
       } 
   
       if ((playBeginTime.Key.Item1 != lastPlayTime.Key.Item1) && (playBeginTime.Key.Item2 != lastPlayTime.Key.Item2)) 
       { 
        int beginTimeInMinutes = playBeginTime.Key.Item1; 
        int endTimeInMinutes = lastPlayTime.Key.Item2; 
   
        int timeResult; 
   
        int beginTimeInHours = Math.DivRem(beginTimeInMinutes, 60, out timeResult); 
        int endTimeInHours = Math.DivRem(endTimeInMinutes, 60, out timeResult); 
   
        Console.WriteLine("Teams play between :: " + beginTimeInHours + " - " + endTimeInHours + "hours"); 
       } 
   } 
   } 
   
   
   internal class TimeRestriction 
   { 
   // 24 hour time slot 12 AM = 0 
   public int startTime { get; set; } 
   
   // 24 hour time slot // 12 PM = 12, 9 PM = 21 
   public int endTime { get; set; }  
   
   public int ConvertToMinutes(int hourTimeSlot) 
   { 
       return (hourTimeSlot * 60); 
   } 
   } 
   
   
   internal class Team 
   { 
       public Team(List<TimeRestriction> teamTimeRestrictions) 
       { 
       TeamTimeRestrictions = teamTimeRestrictions; 
       AvailableSlot = new Dictionary<Tuple<int, int>, bool>(); 
       } 
   
   public Dictionary<Tuple<int, int>, bool> AvailableSlot { get; set; } 
   
   public List<TimeRestriction> TeamTimeRestrictions { get; set; } 
   
   
   public void CreateSlotDictionary() 
   { 
       int beginTime = 0; 
       int endTime = 1440; 
   
       for (int slotTime = beginTime; slotTime < endTime; slotTime++) 
       { 
        Tuple<int, int> timeTuple = new Tuple<int, int>(slotTime, slotTime + 1); 
        AvailableSlot.Add(timeTuple, true); 
       } 
   
       // Apply Restrictions 
       foreach(TimeRestriction currentRestriction in TeamTimeRestrictions) 
       { 
        for(int currentTime = currentRestriction.ConvertToMinutes(currentRestriction.startTime); 
         currentTime < currentRestriction.ConvertToMinutes(currentRestriction.endTime); currentTime++) 
        { 
         Tuple<int, int> restrictionTimeTuple = new Tuple<int, int>(currentTime, currentTime + 1); 
         AvailableSlot[restrictionTimeTuple] = false; 
        } 
       } 
   
   } 
   }