title: Minimize (firstA_max - firstA_min) + (secondB_max - secondB_min)
body: <p>Given n pairs of integers. Split into two subsets A and B to minimize sum(maximum difference among first values of A, maximum difference among second values of B).</p>
  <hr />
  <p>Example : n = 4<br/>
  {0, 0}; {5;5}; {1; 1}; {3; 4}</p>
  <p>A = {{0; 0}; {1; 1}}<br/>
  B = {{5; 5}; {3; 4}}<br/>
  (maximum difference among first values of A, maximum difference among second values of B).</p>
  <p>(maximum difference among first values of A) = fA_max - fA_min = 1 - 0 = 1<br/>
  (maximum difference among second values of B) = sB_max - sB_min = 5 - 4 = 1<br/>
  Therefore, the answer if 1 + 1 = 2. And this is the best way.</p>
  <hr />
  <p>Obviously, maximum difference among the values equals to (maximum value - minimum value). Hence, what we need to do is find the minimum of (fA_max - fA_min) + (sB_max - sB_min)</p>
  <p>Suppose the given array is arr[], first value if arr[].first and second value is arr[].second.</p>
  <p>I think it is quite easy to solve this in quadratic complexity. You just need to sort the array by the first value. Then all the elements in subset A should be picked consecutively in the sorted array. So, you can loop for all ranges [L;R] of the sorted. Each range, try to add all elements in that range into subset A and add all the remains into subset B.<br/>
  For more detail, this is my C++ code</p>
  <pre class="lang-cpp prettyprint-override"><code>int calc(pair&lt;int, int&gt; a[], int n){
      int m = 1e9, M = -1e9, res = 2e9; //m and M are min and max of all the first values in subset A 
      for (int l = 1; l &lt;= n; l++){
          int g = m, G = M; //g and G are min and max of all the second values in subset B
          for(int r = n; r &gt;= l; r--) {
              if (r - l + 1 &lt; n){
                  res = min(res, a[r].first - a[l].first + G - g);
              }
              g = min(g, a[r].second);
              G = max(G, a[r].second);
          }
          m = min(m, a[l].second);
          M = max(M, a[l].second);
      }
      return res;
  }
  </code></pre>
  <hr />
  <p>Now, I want to improve my algorithm down to loglinear complexity. Of course, sort the array by the first value. After that, if I fixed fA_min = a[i].first, then if the index i increase, the fA_max will increase while the (sB_max - sB_min) decrease.</p>
  <p>But now I am still stuck here, is there any ways to solve this problem in loglinear complexity?</p>