Schedule timer 2s memory 1024MB

The Institute for Creative Product Combinations (ICPC) tries to find unusual and innovative ways to unite seemingly unrelated products or technologies, opening up new markets and creating new jobs. (For instance, their most recent success was the “hairbachi,” a hair-dryer with a hibachi grill top attachment for preparing on-the-go hot meals.) The company employs n teams of size 2 to research individual products, then members of the different teams get together to explore ways of combining products.

During the pandemic, the ICPC management organized everyone’s schedule in such a way that there were never more than n people in the office at the same time, and things ran so smoothly that they continued the process once things began to return to normal. Here is the scheme they used. Label the teams with integers 1 through n and the two people on the ith team as (i,1) and (i,2) for each i from 1 to n. Each week, exactly one person from each team is allowed in the office, while the other has to stay away. The employees (i,1) and (i,2) know each other well and collaborate productively regardless of being isolated from each other, so members of the same team do not need to meet in person in the office. However, isolation between members from different teams is still a concern.

Each pair of teams i and j for i≠j has to collaborate occasionally. For a given number w of weeks and for fixed team members (i,a) and (j,b), let w_1<w_2<⋯<w_k be the weeks in which these two team members meet in the office. The isolation of those two people is the maximum of

{ { w1,w2−w1,w3−w2,…,wk−wk−1,w+1−wk } },

or infinity if those two people never meet. The isolation of the whole company is the maximum isolation across all choices of  i, j, a, and b.

You have been tasked to find a weekly schedule that minimizes the isolation of the whole company over a given number w of weeks.