package leetcode;

import java.util.*;

public class ConsistentHash {

public List<List<Integer>> consistentHashing(int n) {

// Write your code here

PriorityQueue<ArrayList<Integer>> pq = new PriorityQueue<ArrayList<Integer>>(n, new Comparator<ArrayList<Integer>>() {

public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {

int diff = (o1.get(1) - o1.get(0)) - (o2.get(1) - o2.get(0));

if(diff == 0){

return o1.get(2) - o2.get(2);

}

else if (diff < 0) {

return 1;

}

else{

return -1;

}

}

});

pq.add(new ArrayList<Integer>(Arrays.asList(0,359,1)));

int maxId = 2;

while(maxId <= n){

ArrayList<Integer> range = pq.poll();

int x = range.get(0);

int y = range.get(1);

int id = range.get(2);

ArrayList<Integer> first = new ArrayList<Integer>(Arrays.asList(x,(x+y)/2,id));

ArrayList<Integer> second = new ArrayList<Integer>(Arrays.asList((x+y)/2+1,y,maxId++));

pq.offer(first);

pq.offer(second);

}

List<List<Integer>> ret = new ArrayList<List<Integer>>();

while(!pq.isEmpty()){

ret.add(pq.poll());

}

Collections.sort(ret, new Comparator<List<Integer>>() {

public int compare(List<Integer> o1, List<Integer> o2) {

return o1.get(0) - o2.get(0);

}

});

return ret;

}

public static void main(String[] args) {

ConsistentHash ch = new ConsistentHash();

for(List<Integer> a:ch.consistentHashing(6)){

System.out.println(a);

}

}

}