MrModest

Yandex - Alrorithm.cs

Jun 5th, 2021
724
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //user1 [(8, 12), (17, 22)]
  2. //user2 [(5, 11), (14, 18), (20, 23), (42, 55)]
  3. //=> [(8, 11), (17, 18), (20, 22)]
  4.  
  5.  
  6. //user1 [(8, 15), (17, 22)]
  7. //user2 [(5, 11), (14, 18), (20, 23), (42, 55)]
  8. //=> [(8, 11), (14, 15), (17, 18), (20, 22)]
  9.  
  10. //user1 [(8, 10), (13, 15)]
  11. //user2 [(11, 12), (16, 18)]
  12. //=> []
  13.  
  14. //user1 [(8, 20), (21, 25)]
  15. //user2 [(11, 12), (16, 18)]
  16. //=>  [(11,12),(16,18)]
  17.  
  18. private static (int start, int end)? GetIntersec((int start, int end) first, (int start, int end) second)
  19. {
  20.     if (first.end < second.first || second.end < first.start)
  21.     {
  22.         return null;
  23.     }
  24.     return (Math.Max(first.start, second.start), Math.Min(first.end, second.end));
  25. }
  26.  
  27. private static List<(int start, int end)> IntersecIntervals((int start, int end)[] user1, (int start, int end)[] user2)
  28. {
  29.     var intervals = new List<(int start, int end)>();
  30.    
  31.     var first = 0;
  32.     var second = 0;
  33.    
  34.     while (first < user1.Length && second < user2.Length)
  35.     {
  36.         var interval = GetIntersec(user1[first], user2[second]);
  37.        
  38.         if (interval != null)
  39.         {
  40.             intervals.Add(interval);
  41.         }
  42.    
  43.         var edge = Max.Min(user1[first].end, user2[second].end);
  44.        
  45.         if (user1[first].end == edge)
  46.         {
  47.             first++;
  48.         }
  49.        
  50.         if (user2[second].end == edge)
  51.         {
  52.             second++;
  53.         }
  54.     }
  55.    
  56.     return intervals;
  57. }
RAW Paste Data