Как найти последний край, соединяющий вершины, путем обхода двух непересекающихся равнозначных наборов вершин

Вы можете сделать это в O(nlogn)

• Сначала отсортируйте оба массива и установите current = 1
• Теперь найдите, какой массив содержит 1, так как вы должны начать со значения 1.
• Теперь найдите позицию current value в противоположном массиве (рядом), используя двоичный поиск в O (logn)
• Найдите разницу между левым и правым соседними значениями и измените текущее значение на значение, которое приводит к наименьшей разнице.
• Конечно, установите все посещенные значения, с которыми вы уже работали. Чтобы вы не работали дважды с одним и тем же значением
• Таким образом, общая сложность составляет O(nlogn).

4-й шаг Проработка:

Предположим, что ваше текущее значение находится в array a, а вы ищете в array b...

current value = 5  
b = { 2 , 3 , 8 , 10}  
            ^

если вы выполните бинарный поиск в массиве b, вы получите позицию 2. А сейчас -

установите current value = 8 и отметьте 8 как посещенные.
Теперь сделайте step 2 and 3 в array a и так далее...

Обновление:

Пример реализации на С++:

#include <bits/stdc++.h>
using namespace std;

vector<int>right_a,right_b;
// Using union_find algorithm to find the next available value(which is not visited)
int find1(int x)
{
    if(x==right_a[x])
      return x;
    right_a[x]=find1(right_a[x]);
}
int find2(int x)
{
    if(x==right_b[x])
      return x;
    right_b[x]=find2(right_b[x]);
}
int main()
{
    int i,j,k,l,m,n=5;

    int a[]={1, 2, 4, 8, 9};
    int b[]={3, 5, 6, 7, 10};

    for(i=0;i<n;i++)
    {
        right_a.push_back(i);
        right_b.push_back(i);
    }

    int cur=1,work_with;
    if(a[0]==cur)
    {
        right_a[0]=1;
        work_with=0;
    }
    else
    {
        right_b[0]=1;
        work_with=1;
    }

    printf("%d",1);
    int cnt=1;
    while(cnt<2*n)
    {
        if(work_with==0)
        {
            // find first relative to actual value in array b
            int ind=lower_bound(b,b+n,cur)-b;
            if(ind==n)
              ind=0;
            ind=find2(ind);
            int next=ind+1;
            if(next==n)
                next=0;
            right_b[ind]=right_b[next]; // making current value visited
            printf(" -> %d",b[ind]);
            cur=b[ind];

            work_with=1;
        }
        else
        {
            // find first relative to actual value in array a
            int ind=lower_bound(a,a+n,cur)-a;
            if(ind==n)
              ind=0;
            ind=find1(ind);
            int next=ind+1;
            if(next==n)
                next=0;
            right_a[ind]=right_a[next]; // making current value visited
            printf(" -> %d",a[ind]);
            cur=a[ind];

            work_with=0;
        }
        cnt++;
    }
    printf("\n");
return 0;
}