Sort

252. Meeting Rooms Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings. Example 1: Input: intervals = [[0,30],[5,10],[15,20]] Output: false Example 2: Input: intervals = [[7,10],[2,4]] Output: true Constraints: 0 <= intervals.length <= 10^4 intervals[i].length == 2 0 <= starti < endi <= 10^6 Solution class Solution { public boolean canAttendMeetings(int[][] intervals) { if (intervals.length < 2) { return true; } Arrays.sort(intervals, (a, b) -> a[0] - b[0]); for (int i = 1; i < intervals.length; i++) { int[] curr = intervals[i]; int[] prev = intervals[i - 1]; if (overlap(prev, curr)) { return false; } } return true; } /* ---------------| |-------------------------- -----------| |-------------- */ boolean overlap(int[] a, int[] b) { return Math.max(a[0], b[0]) < Math.min(a[1], b[1]); } }

253. Meeting Rooms II Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required. Example 1: Input: intervals = [[0,30],[5,10],[15,20]] Output: 2 Example 2: Input: intervals = [[7,10],[2,4]] Output: 1 Constraints: 1 <= intervals.length <= 10^4 0 <= starti < endi <= 10^6 Solution class Solution { /* [[0,30],[5,10],[15,20]] [ 0,30] [ 5,10] ---- [15,20] (1, 10), (2, 7), (3, 19), (8, 12), (10, 20), (11, 30) */ public int minMeetingRooms(int[][] intervals) { Arrays.sort(intervals, (a,b) -> a[0] - b[0]); PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a,b) -> { return a[1] - b[1]; }); for (int[] interval: intervals) { if (!pq.isEmpty() && pq.peek()[1] <= interval[0]) { pq.poll(); } pq.add(interval); } return pq.size(); } } Solution 2 class Solution { public int minMeetingRooms(int[][] intervals) { Integer min = Integer.MAX_VALUE; Integer max = Integer.MIN_VALUE; for (int[] i: intervals) { min = Math.min(min, i[0]); max = Math.max(max, i[1]); } int[] times = new int[max - min + 1]; for (int[] i: intervals) { times[i[0] - min]++; times[i[1] - min]--; } int count = 0; int result = 0; for (int time: times) { count += time; result = Math.max(result, count); } return result; } }

791. Custom Sort String You are given two strings order and s. All the words of order are unique and were sorted in some custom order previously. Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string. Return any permutation of s that satisfies this property. ...

977. Squares of a Sorted Array Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. Example 1: Input: nums = [-4,-1,0,3,10] Output: [0,1,9,16,100] Explanation: After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100]. Example 2: Input: nums = [-7,-3,2,3,11] Output: [4,9,9,49,121] Constraints: 1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums is sorted in non-decreasing order. Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach? ...

1329. Sort the Matrix Diagonally A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix’s end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2]. Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix. ...

1877. Minimize Maximum Pair Sum in Array The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs. For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8. Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that: ...

149. Max Points on a Line Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line. Example 1: Input: points = [[1,1],[2,2],[3,3]] Output: 3 Example 2: Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Constraints: 1 <= points.length <= 300 points[i].length == 2 -104 <= xi, yi <= 104 All the points are unique. /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode sortedArrayToBST(int[] nums) { if (nums.length == 0) return null; return buildBST(nums, 0, nums.length - 1); } TreeNode buildBST(int[] nums, int lo, int hi) { if (hi < lo) { return null; } TreeNode node = new TreeNode(); int mid = lo + (hi - lo) / 2; node.val = nums[mid]; node.left = buildBST(nums, lo, mid - 1); node.right = buildBST(nums, mid + 1, hi); return node; } }

![https://leetcode.com/problems/insert-interval/] Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Example 2: Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10]. Example 3: Input: intervals = [], newInterval = [5,7] Output: [[5,7]] Example 4: Input: intervals = [[1,5]], newInterval = [2,3] Output: [[1,5]] Example 5: Input: intervals = [[1,5]], newInterval = [2,7] Output: [[1,7]] Constraints: ...

![https://leetcode.com/problems/sort-the-matrix-diagonally/] A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix’s end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2]. Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix. ...

![https://leetcode.com/problems/sort-colors/] Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. Example 1: Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Example 2: Input: nums = [2,0,1] Output: [0,1,2] Example 3: Input: nums = [0] Output: [0] Example 4: Input: nums = [1] Output: [1] Constraints: ...