meetup

package com.ie.ng.jobsearch.common.common;

import java.util.LinkedList;
import java.util.Queue;
import javax.persistence.criteria.CriteriaBuilder.In;

public class Test {

  public static void main(String[] args) {
//    int[] start = {1,2,1,2,2};
//    int[] end = {3,2,1,3,3};
    int[] start = {1,8,8};
    int[] end = {1,8,8};
    int ans = new Test().meetup(start,end);
    System.out.println(ans);
  }

  public int meetup(int[] start, int[] end){
    int n = start.length;
    int[][] arr = new int[n*2][2];
    int i=0;
    for(int j=0;j<n;j++){
      arr[i][0]=start[j];
      arr[i][1]=0;
//      arr[i][2]=end[j];
      i++;
    }
    for(int j=0;j<n;j++){
      arr[i][0]=end[j];
      arr[i][1]=1;
//      arr[i][2]=start[j];
      i++;
    }
//    System.out.println(arr);
    sort(arr,0,n*2-1);
//    System.out.println(arr);

    int min = arr[0][0];
    int ans=0;
    Queue<Integer> queue = new LinkedList<>();

    for(i=0;i<arr.length;i++){
      if(arr[i][1]==1){
        if(min<queue.peek()){
          min=queue.peek();
        }
        queue.remove();
        //is end ele
        if(min>arr[i][0]) {
          continue;
        }else{
          min++;
          ans++;
        }
      }
      else{
        //is start ele
        queue.add(arr[i][0]);
      }
    }


    return ans;
  }

  void merge(int arr[][], int l, int m, int r)
  {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[][] = new int[n1][2];
    int R[][] = new int[n2][2];
    for (int i = 0; i < n1; ++i) {
      L[i][0] = arr[l + i][0];
      L[i][1] = arr[l + i][1];
//      L[i][2] = arr[l + i][2];
    }
    for (int j = 0; j < n2; ++j) {
      R[j][0] = arr[m + 1 + j][0];
      R[j][1] = arr[m + 1 + j][1];
//      R[j][2] = arr[m + 1 + j][2];
    }

    int i = 0, j = 0;
    int k = l;
    while (i < n1 && j < n2) {
      if (L[i][0] < R[j][0] || L[i][0] == R[j][0] && L[i][1] < R[j][1]) {
        arr[k][0] = L[i][0];
        arr[k][1] = L[i][1];
//        arr[k][2] = L[i][2];
        i++;
      }
      else {
        arr[k][0] = R[j][0];
        arr[k][1] = R[j][1];
//        arr[k][2] = R[j][2];
        j++;
      }
      k++;
    }
    while (i < n1) {
      arr[k][0] = L[i][0];
      arr[k][1] = L[i][1];
//      arr[k][2] = L[i][2];
      i++;
      k++;
    }

    while (j < n2) {
      arr[k][0] = R[j][0];
      arr[k][1] = R[j][1];
//      arr[k][2] = R[j][2];
      j++;
      k++;
    }
  }

  void sort(int arr[][], int l, int r)
  {
    if (l < r) {
      int m = (l + r) / 2;
      sort(arr, l, m);
      sort(arr, m + 1, r);
      merge(arr, l, m, r);
    }
  }

}