Divide Intervals Into Minimum Number of Groups

 Divide Intervals Into Minimum Number of Groups
 Leetcode Problem Divide Intervals Into Minimum Number of Groups  is very much similar to the number-of-the-smallest-unoccupied-chair Here we have to divide the given intervals into minimum number of groups such that each interval is in exactly one group, and no two intervals that are in the same group intersect each other.

Solution: We will think each interval as combination of two events,  startTime and endTime.
1) We create a list of events and then sort that list. 

2) After that, we Initialise a min heap. which can be thinked like different baskets or groups. 

3) We iterate through the events one by one, and assign each events to groups (picked from minheap).
     While iterating starting event we pick a group from min heap and keep track in an array. 
     While iterating ending event through our tracking array, we release the group again in min heap.
     During this process, we track what is the maximum group number poped from min heap.
    and that will be going to be the answer of our problem statement.

class Solution {

public int minGroups(int[][] intervals) {

List<int[]> events = new ArrayList<>();

for(int i=0;i<intervals.length;i++) {

events.add(new int[]{intervals[i][0], i, 0});

events.add(new int[]{intervals[i][1], i, 1});

}

Collections.sort(events, (a, b) -> {

if(a[0]==b[0]) {

return a[2]-b[2];

}

return a[0] - b[0];

});

PriorityQueue<Integer> baskets = new PriorityQueue<>();

for(int i=1;i<=intervals.length;i++) {

baskets.add(i);

}

int[] capBasket = new int[events.size()];

int ans = 0;

for(int i=0;i<events.size();i++) {

int st = events.get(i)[0];

int ind = events.get(i)[1];

int ty = events.get(i)[2];

if(ty==0) {

capBasket[ind] = baskets.poll();

} else {

baskets.add(capBasket[ind]);

}

ans = Math.max(ans, capBasket[ind]);

}

return ans;

}

}