sort

*sort.py

973. K Closest Points to Origin
https://leetcode.com/problems/k-closest-points-to-origin/
We have a list of points on the plane.  Find the K closest points to the origin (0, 0).
(Here, the distance between two points on a plane is the Euclidean distance.)
You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)
Example 1:
Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        PriorityQueue<int[]> pq= new PriorityQueue<int[]> ( (p1, p2)-> p2[0]*p2[0] + p2[1]*p2[1] - p1[0]*p1[0] - p1[1]*p1[1] );
        
        for(int[] p: points){
            pq.add(p);
            if(pq.size() > K) pq.poll();
        }
        
        int[][] ans= new int[K][2];
        
        while (K > 0) {
            System.out.println(K);
            ans[--K] = pq.poll();
        }
        
        // for(int i=0; i< K; i++){
        //     System.out.println(i);
        //     ans[i]= pq.poll();
        // }
        
        return ans;  
        
        //sort nlog(n)
        //Arrays.sort( points, (p1, p2)->  p1[0]*p1[0] + p1[1]*p1[1] - p2[0]*p2[0] - p2[1]*p2[1] );
        //return Arrays.copyOfRange(points, 0, K);
    }
}

937. Reorder Log Files
https://leetcode.com/problems/reorder-log-files/
You have an array of logs.  Each log is a space delimited string of words.
For each log, the first word in each log is an alphanumeric identifier.  Then, either:
Each word after the identifier will consist only of lowercase letters, or;
Each word after the identifier will consist only of digits.
We will call these two varieties of logs letter-logs and digit-logs.  
It is guaranteed that each log has at least one word after its identifier.
Reorder the logs so that all of the letter-logs come before any digit-log.  
The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties.  
The digit-logs should be put in their original order.
Return the final order of the logs.
Example 1:
Input: ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]
    
class Solution {
    //nlogn
    public String[] reorderLogFiles(String[] logs) {
   	Arrays.sort(logs, ( logs1, logs2) -> {
    		String[] splitter1= logs1.split(" ",2);
    		String[] splitter2= logs2.split(" ",2);

    		if( Character.isDigit(splitter1[1].charAt(0)) && Character.isDigit(splitter2[1].charAt(0)) ) return 0;// no order
    		if( Character.isLetter(splitter1[1].charAt(0)) && Character.isDigit(splitter2[1].charAt(0)) ) return -1;//
    		if( Character.isDigit(splitter1[1].charAt(0)) && Character.isLetter(splitter2[1].charAt(0)) ) return 1;
    		
  		return  splitter1[1].equals( splitter2[1])  ? 
                	splitter1[0].compareTo(splitter2[0] ) : splitter1[1].compareTo(splitter2[1]);
    	});
    	
		System.out.println( Arrays.toString(logs) );
    	return logs;        
    }
}    
    

meeting room.py

253. Meeting Rooms II
https://leetcode.com/problems/meeting-rooms-ii/
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), 
find the minimum number of conference rooms required.
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
Example 2:
Input: [[7,10],[2,4]]
Output: 1
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
  
class Solution {
    // O(Nlog N)
    public int minMeetingRooms(int[][] intervals) {
        if(intervals==null || intervals.length==0) return 0; 
        
        Arrays.sort(intervals, (int[] a, int[] b)-> a[0]-b[0] );
    	PriorityQueue<Integer> minHeap= new PriorityQueue<>();
    	minHeap.add(intervals[0][1]);
    	
    	for(int i=1; i<intervals.length; i++) {
    		if( minHeap.peek() <= intervals[i][0])  minHeap.remove();
    		minHeap.add(intervals[i][1] );
    	}
    	return minHeap.size();
    }
}
      
56. Merge Intervals
https://leetcode.com/problems/merge-intervals/description/
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.  
  
class Solution {
    //O(nlogn)
    public int[][] merge(int[][] intervals) {
        if(intervals.length==0) return intervals;
        
        Arrays.sort(intervals, (int[] a, int[] b)-> a[0]-b[0]);
        
        List<int[]> list = new ArrayList<>();
        int[] last = null;
        for( int[] interval : intervals) {
            if (  last==null || interval[0]>last[1] ) {//--------here---------
            	list.add(interval);
                last = interval;
            } else 
            	last[1] = interval[1] > last[1] ? interval[1]:last[1];//--------here---------
        }
        
        int[][] ans= new int[list.size()][];
        for(int i=0; i<list.size(); i++)
      	ans[i]= list.get(i);
		
    	return ans;
    }
}