Scheduling algorithm. Date period

Question

Good day. Help please build an algorithm. There is an array of flights, below one of the flights.

2017/2018 = год 1..52 = номера недель 1..7 номера дней

that is, the record 2017=> { 8=>[2, 5, 7] } means that the flight makes a flight in 2017 on the 8th week, on Tuesday, Friday and Sunday

 hash = { :airline=>'U6', :flight_number=>'873', :origin=>'PEK', :destination=>'BKK', :dates=>[ { 2017=> { 8=>[2, 5, 7], 9=>[2, 5, 7], 10=>[2, 5, 7], 11=>[2, 5, 7], 12=>[1, 2, 5, 7], 13=>[2, 5, 7], 14=>[2, 5, 7], 15=>[2, 5], 27=>[2, 5, 7], 28=>[2, 5, 7], 29=>[2, 5, 7], 30=>[2, 5, 7], 31=>[2, 5, 7], 32=>[2, 5, 7], 33=>[2, 5, 7], 34=>[2, 5, 7], 35=>[2], 49=>[5, 7], 50=>[2, 5, 7], 51=>[2, 5, 7], 52=>[2, 5, 7] } }, { 2018=>{ 1=>[2, 5, 7], 2=>[2, 5, 7], 3=>[2, 5, 7], 4=>[2, 5, 7], 5=>[2, 5, 7], 6=>[2, 5, 7], 7=>[2, 5, 7], 8=>[2, 5, 7], 9=>[2, 5, 7], 10=>[2, 5, 7], 11=>[2, 5, 7], 12=>[2, 5] } } ] }

I can not think of an algorithm, how to decompose the hash into four periods

 U6 873 PEK BKK -2--5-7 2017/02/21 - 2017/04/14 (- 8..15 недели) U6 873 PEK BKK 1------ 2017/03/20 - 2017/03/20 (- 12 неделя) U6 873 PEK BKK -2--5-7 2017/07/04 - 2017/08/29 (- 27..35 недели) U6 873 PEK BKK -2--5-7 2017/12/08 - 2018/03/23 (- 49..52..1..12 недели)

I don’t know how to cut it, but I’d probably walked through the hash of weeks in order of increasing the key would memorize the current value of the array element for the future and check the current value with the memorized one and, if it were, it would increase the end date.
if the values are different, then we write the accumulated period to the output and begin to memorize the new one, i.e.
Because, probably, you yourself have not yet decided what you want :) If you want to calculate periods with a constant weekly schedule, then you will have not 4, but 9 (!).
Hmm, although I seem to have figured out now what you mean, you want the periods to start and end in the middle of the week, as well as allow intersections.
But in this case we are not talking directly about the weeks, but about the date ranges with the days of the week .

Yuri Negometyanov Yuri Negometyanov 4,921 12 39 · Accepted Answer · 2017-02-28T19:08:29

Combine weeks into a common array. Desired result:

 : dates_2017_2018 = [
     8 => [2, 5, 7],
 ...
     52 => [2, 5, 7],
     53 => [2, 5, 7]
 ... 
     63 => [2, 5, 7]
     64 => [2, 5]
 ]

Note that in the future, the year does not always end on Sunday.

Build periods for each day of the week, considering Monday as the zero day of the week. Desired result:

 : periods_2017_2018 = [
   {
      1 =>
         {
           [12 * 7.12 * 7]
         },
      2 =>
         {
           [8 * 7 + 1, 15 * 7 + 1],
           [27 * 7 + 1, 35 * 7 + 1],
           [50 * 7 + 1, 64 * 7 + 1]
         },
      5 =>
         {
           [8 * 7 + 4, 15 * 7 + 4],
           [27 * 7 + 4, 34 * 7 + 4],
           [49 * 7 + 4, 64 * 7 + 4]
         },
      7 =>
         {
           [8 * 7 + 6, 14 * 7 + 6],
           [27 * 7 + 6, 34 * 7 + 6],
           [49 * 7 + 6, 63 * 7 + 6]
         }
   }
 ]

Only 10 periods.

Glue the resulting subarrays according to the algorithm:

A. Initialization: id1=1 .

B. For each period from the subarray with id1 to carry out pasting with the periods of the subarrays following it.

B1. For each id2>id1 :

B1.1. Create a subarray with id3 = 10*id1+id2 .

B1.2. Check the gluing conditions with each period of the subarray.

Bonding condition: the difference between the beginnings of periods of not more than 6 days and between the ends, too.

If the gluing condition is fulfilled, then:

in the id3" subarray id3" write down the earlier beginning and later end of the glued periods;
remove glued periods from both subarrays.

B1.3. If at the end of p. B1.2 the subarray with id3" empty, it should be deleted. If it is not empty, then set the change flag.

B2. If the change flag is set, then delete all empty subarrays and write ready="id1" .

B3. Sort the indices of the subarrays in alphabetical order (1, 12, 2, ..) and look for the id1 index following the ready .
If such an index is found, then go to step 3.

Desired result:

 : periods_2017_2018 = [
   {
      1 =>
         {
           [12 * 7.12 * 7]
         },
      257 =>
         {
           [8 * 7 + 1, 15 * 7 + 4],
           [27 * 7 + 1, 35 * 7 + 1],
           [49 * 7 + 4, 64 * 7 + 4]
         }
   }
 ]

And it remains only to form a report.

Scheduling algorithm. Date period

1 answer 1

More articles: