# 20191125

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:
Input: s = "rat", t = "car"
Output: false

Example 3:
Input: s = "apple", t = "elppa"
Output: true

Note:
You may assume the string contains only lowercase alphabets.

public boolean isAnagram(String s, String t) {
    if (s.length() == 0 && t.length() == 0) {
       return true;
    } else if (s.length() == 0 && t.length != 0) {
       return false;
    } else if (s.length() != 0 && t.length == 0) {
       return false;
    }
    
//    if (s.length() != t.length()) {
//        return false;
//    }
    
    char[] sc = s.toCharArray();
    Arrays.sort(sc);
    char[] tc = s.toCharArray();
    Arrays.sort(tc);
    return sc.toString().equals(tc.toString());
    
    String str1 = new String(sc);
    String str2 = new String(tc);
    
    return str1.equals(str2);
    
    // return Arrays.equals(sc, tc);
}

Given a collection of intervals, merge all overlapping intervals.

Example 1:
The sencond element of the fisrt array in this two dimension array.
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].

result = [[1,3], [8,10]]
newInterval = [1,6]
newInterval[1] = 6
newInterval = interval
result.add(newInterval);
        
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]

Input: [[1, 2], [3, 4]]
Output: [[1, 2], [3, 4]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

public int[][] merge(int[][] intervals) {
    if (intervals == null) return new int[][]{{}};
    if (intervals.length <= 1) return intervals;
    
    Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0], i2[0]));
    
    // Input: [[1,3],[2,6],[8,10],[15,18]]
    List<int[]> result = new ArrayList<>();
    int[] newInterval = intervals[0]; // [15,18]
    result.add(newInterval); // [[1,6], [8,10], [15, 18]]
    for (int[] interval : intervlas) {
        if (interval[0] <= newInterval[1]) {
            newInterval[1] = Math.max(interval[1], newInterval[1]);
        } else {
            newInterval = interval;
            result.add(newInterval);
        }
    }
    
    return result.toArray(new int[result.size()][]);
}

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.)
 

Note:
1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

public int[][] kClosest(int[][] points, int K) {
    if (points.length == 1) return points;
    
    PriorityQueue<int[]> minHeap = new PriorityQueue<>(a, b) -> (a[0] * a[0] + a[1] * a[1]) - (b[0] * b[0] + b[1] * b[1]));
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> (b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1]));
    
    // maxHeap
    // minHeap(default)
    
    for(int[] point: points) {
        queue.offer(point);
        if (queue.size() > K) {
            queue.poll();
        }
    }
    
    int[][] result = new int[K][2];
    while(!queue.isEmpty()) {
        result[queue.size() - 1] = queue.poll();
    }
    
    return result;
}

max = 5
Set<Integer> seen =

1 1 1 1
2 2 1 3
3 1 1 3

public void dfs(int[][] graph)

[[1,3],[2,6],[8,10],[15,18]]
1 --- 3
2 ------- 6
8 --- 10
15 --- 18

x
start [1, 2, 8, 15]
end [3, 6, 10 , 18]
x

1 ------3
2 ------- 6
8 --- 10
15 --- 18
x
start [1, 2, 8, 15]
end [6, 10 , 18, 20]
x

i = 3
j = 3

x
start [1, 2, 8, 15]
end [6, 7, 10, 18]
x
[1, 7][8, 10][15, 18]

[[1,7],[2,6],[8,10],[15,18]]
1 ----------- 7
2 ------- 6
8 --- 10
15 --- 18

for (int i = 0, j = 0; i < n; i++) { // j is start of interval.
	if (i == n - 1 || starts[i + 1] > ends[i]) {
		res.add(new Interval(starts[j], ends[i])); 
		j = i + 1; 
	}
}