Make Best Use of the Conference Room

Problem: Given a conference room and a number of presentations with start and end time ( e.g., [4, 9], [5, 10]), try to make an arrangement which allows the conference room to be used for maximum time. Overlapping presentations can't be in the same arrangement.

Solution: We can have a O(nlogn) solution by using DP.  The details are as follows:

• Sort the presentations by their end time. Thus we will have a sorted array end[N].   N is the number of the presentations.
• Have an array Max_arr[N].  Max_arr[i] stands for if we take end[i] as the close time for the conference room, the maximum time the room can be used. It is easy to know that  Max_arr[0] = the duration of the presentation that ends at  end[0]. We need to find out Max_arr[N-1].
• To calculate Max_arr[i], we first get the start time si of the presentation that ends at end[i]. Then we do binary search in end[0] ... end[i-1] for si. Basically we need to find a j such that  end[j] < si &&  end[j+1] > si. Therefore,  Max_arr[i] = max(Max_arr[i-1],  Max_arr[j] + end[i] -  si ).

Find K Elements with Maximum Minimum Consecutive Difference

Problem: Given a sorted array A, find k elements from the array with the maximized minimum consecutive difference. For example, m1, ... , mk are selected elements. We want to maximize min(mi+1-mi). A more concrete example, a sorted array A = [1, 3, 4, 8] and k =3. There are four ways of picking 3 elements: {1,3,4}, {1, 4, 8}, {1, 3, 8}, {3, 4, 8}. The minimum consecutive difference for these four selections are 2, 3, 2, 1, respectively. The maximum of these minimum consecutive differences is 3, which is from selection {1, 4, 8}.


Solution: [*will re-edit later*] This is problem is similar to given a line, try to divide the line into several segments as even as possible. It is also similar to the "Painter and Slates" problem (see a link here). The key here is to use binary search, which will give you O(nlog(A[n-1] - A[0])). Using DP definitely is OK, but the complexity is O(k*n^2).

• Basically, the selection depends on the how "wide" the gap we use. If we use the gap as wide as A[n-1] - A[0] (n is the size of array), we can only select 2 elements. On the other way, if we choose the gap as min(A[i+1]-A[i]), we will select n elements. Our goal is to select k elements while with maximized minimum difference. k is within 2 and  n. Then a binary search can help us find k.
• We just do binary search on the space of the width of the gap. We set low =  min(A[i+1]-A[i]), high =  A[n-1] - A[0] and make mid = (low + high) /2. 
• With this mid as the width of the gap, we can calculate the number of elements we selected. If it is larger than k, we need to increase the width of the gap: we just update low = mid; Otherwise, we need to decrease the width of the gap by update high = mid.
• We stop when we find a gap such that if we further increase the gap, we can't be able to select k elements.
• Try to calculate m[i][j][k], where i and j are the index within A[] and k how many elements are selected with in the region A[i] ~ A[j]. The time to calculate this array is O(N^4). 

Find the Kth Smallest Element of Two Sorted Arrays

Problem: given two sorted arrays, find the Kth smallest element.

Solution: if we have two pointer scanning from the heads of two arrays, we can have an O(K) algorithm. Here we give the main idea of an O(logm + logn) algorithm, where m and n are the length of the two arrays, respectively.

1. We pick the ith and jth elements from two arrays. We make i+j = K-1. Then if Ai > Bj && Ai < Bj+1, Ai is the Kth smallest element. The other way is the same (Ai < Bj).
2. If the previous condition doesn't hold, which means Ai < Bj && Ai < Bj+1. Then the Kth smallest element cannot be within A0 to Ai and Bj+1 to Bn-1. Then we remove them and only need to look for the K-i-1th smallest element in the sub-arrays left.

Find the Median of Two Sorted Arrays

Problem: given two sorted arrays, find the median.

Solution: Assume the length of the two arrays are m and n. When m+n is even, the median is the average of two numbers. The neat solution has a time complexity of O(log(m+n)). Basically, we need to leverage binary search. The details of this algorithm is very complex due to many corner cases to handle. The following just gives the main idea.

1. get the median of two arrays Ai and Bj, where i = m/2 and j = n/2. If  Ai <= Bj, the median will be between Ai and Bj.
2. therefore, we can discard A0 to Ai-1 and Bj+1 to Bn-1. However, we cannot do this in a naive way. To reduce to an equivalent sub-problem, we need to discard the same number of elements from each array. Then we keep comparing the middle elements of the sub-arrays. To discard the same number of elements, we just need to get Min(i, n-j-1).

Besides, we can also use the techniques in Find the Kth Smallest Element of Two Sorted Arrays.

More: a more general problem is to find the median for K sorted arrays. There are two ways:

1. Guess a number, search each array to see how many elements are smaller than this number. Then we can have a total number. If this total is smaller than half, we guess a bigger number; otherwise, we guess a smaller number. Try to repeat binary search until our goal is met.
2. The second approach is to first find the medians of all the arrays. Then we can know the bounds of these medians (low_m, high_m). For each array, throw the elements that are out of the bounds. Make sure the elements thrown at the two ends of the array should be the same number. Then repeat until our goal is met.

Find the Super Cool Number

Problem: A Super Cool number is a nature number which can be represented as a^b (a and b are both nature number and b>1. Given a nature number N, find the super cool number that is closest to N.

Solution: The key is to know the upper bound of the exponent, ceiling (log_2_(N)). If we have functions such as log(), then it is easy. Otherwise, we need to guess an upper bound, we can use N/2.  Then we do a series of binary search,

• find a value n between 1 and N such that n^exponent is closest to N.
• for all the possible exponent, repeat the previous step.
• binary search over the exponent is quicker than search over the base (i.e., 1~N)

Then the total complexity is around O(logN*logN).

Next Permutation of an Integer or string

Problem: Given an integer(or string), get the integer that is just bigger than it (lexicographical order).

Example:  given 507632, we need find 520367; given 123, we need find 1023.  

Solution: Basically, we need something like next_permutation in STL, but we can implement by our own.

1. Start from the end, we try to find the longest non-increasing sequence. Then the integer (or string) is divided into halves. For the tail part, we can't find one that is bigger than it. Then we need to think of the front part.
2. We swap the last element a of the front part with the element b in the tail part that is the smallest one but bigger than a. swap a and b. The tail part is still a non-increasing sequence. We just reverse it and append it to the front part. The reverse is neat!
3. for the case where the integer (or string) is already the biggest one, we need to add zero.

The code is as follow (not consider the case that needs adding zero):

char* next_perm(char* s, int len)
{

    int i = len-1;

    while(i>=1 && s[i-1] >= s[i])
          i--;

    if(i==0)  return 0;

    int lo = i;
    int hi = len - 1;
    
    //binary search
    int c = s[i-1];
    
    while(lo < hi)
    {
      int mid = lo + (hi - lo)/2;
      if(s[mid] <= c)
           hi = mid-1;
      else if(s[mid] > c)
      {     
         if(mid+1 <= hi && s[mid+1] <=c)
         {   
           lo = mid;
           break;
         }
         lo = mid+1;
      }
    
    }
    
    s[i-1] = s[lo];
    s[lo] = c;

    //reverse
    lo = i;
    hi = len - 1;

    while(lo<hi)
    {
       char t = s[lo];
       s[lo] = s[hi];
       s[hi] = t;
       lo++;
       hi--;
    }

    return s;
}