Sorting and Searching Part 2: Medium

Merge Intervals

class Solution {
    public int[][] merge(int[][] intervals) {
        
        Arrays.sort(intervals, (i1, i2) -> i1[0] - i2[0]);
        
        List<int[]> result = new ArrayList<int[]>();
        
        if (intervals.length <= 1) {
            return intervals;
        }
        
        result.add(intervals[0]);
        
        for (int i = 1; i < intervals.length; i++) {
            if (result.get(result.size() - 1)[1] >= intervals[i][0]) {
                if (result.get(result.size() - 1)[1] < intervals[i][1]) {
                    int[] prev = result.remove(result.size() - 1);
                    prev[1] = intervals[i][1];
                    result.add(prev);
                }
                
            } else if (result.get(result.size() - 1)[1] < intervals[i][0]) {
                result.add(intervals[i]);
            }
        }
        
        
        return result.toArray(new int[result.size()][]);
    }
}

애매하게 이상하게 계속 걸려서 빡쳤네요^^

class Solution {
	public int[][] merge(int[][] intervals) {
		if (intervals.length <= 1)
			return intervals;

		// Sort by ascending starting point
		Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0], i2[0]));

		List<int[]> result = new ArrayList<>();
		int[] newInterval = intervals[0];
		result.add(newInterval);
		for (int[] interval : intervals) {
			if (interval[0] <= newInterval[1]) // Overlapping intervals, move the end if needed
				newInterval[1] = Math.max(newInterval[1], interval[1]);
			else {                             // Disjoint intervals, add the new interval to the list
				newInterval = interval;
				result.add(newInterval);
			}
		}

		return result.toArray(new int[result.size()][]);
	}
}

Search in a Rotated Sorted Array

class Solution {
    public int search(int[] nums, int target) {
        // if it decreases, that's the pivot
        // first value - smallest of the largest, last value - largest of the smallest
        
        int pivot = -1;
        int s = 0, e = nums.length - 1;
        int m = (s + e) / 2;
        
        int first = nums[0];
        int last = nums[e];
        
        int loc = -1; 
        
        if (last < first) {
            
            while (nums[m] < nums[m+1]) {
                if (nums[m] < first) {
                    e = m;
                } else {
                    s = m; 
                }
                
                m = (s + e) / 2;
            }
            
            pivot = m + 1;
            
        } else {
            pivot = 0; 
        }
        
        if (target > last) {
            s = 0;
            e = pivot - 1;
        } else {
            s = pivot;
            e = nums.length - 1; 
        }
        
        
        while (s <= e) {
            m = (s + e) / 2;
            if (nums[m] == target) {
                return m;
            } else {
                if (nums[m] < target) {
                    e = m;
                } else {
                    s = m; 
                }
            }
        }
        
        return -1;
        
    }
}

Time Limit Exceeded

class Solution {
    public int search(int[] nums, int target) {
        int s = 0;
        int e = nums.length - 1;
        
        while (s <= e) {
            int m = s + (e - s) / 2;
            
            if (nums[m] == target) return m;
            else if (nums[s] <= nums[m]) {
                if (nums[s] <= target && target < nums[m]) {
                    e = m - 1;
                } else {
                    s = m + 1;
                }
            } else {
                if (nums[e] >= target && target > nums[m]) {
                    s = m + 1;
                } else {
                    e = m - 1;
                }
            }
        }
        
        return -1; 
    }
}

원래 루션이
훨씬 간단하네요^^

원래는 앞부분 pivot 뒤지면서 value 뒤지기 + 그 후에 binary search로 하려고 했는데 둘 다 binary search로 함

Meeting Room II

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        
        if (intervals.length < 1) {
            return 0; 
        }
        
        Arrays.sort(intervals, (n1, n2) -> n1[0] - n2[0]);
        
        Queue<Integer> ending = new PriorityQueue<Integer>();
        
        ending.add(intervals[0][1]);
        int rooms = 1;
        int taken = 1;
        
        for (int i = 1; i < intervals.length; i++) {
            int start = intervals[i][0];
            
            for (int x : ending) {
                if (x <= start) {
                    ending.poll();
                    taken--;
                }
            }
            
            ending.add(intervals[i][1]);
            taken++;
            
            rooms = Math.max(rooms, taken);
            
        }
        
        return rooms;
    }
}

concurrent modification exception

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        
        if (intervals.length < 1) {
            return 0; 
        }
        
        Arrays.sort(intervals, (n1, n2) -> n1[0] - n2[0]);
        
        Queue<Integer> ending = new PriorityQueue<Integer>();
        
        ending.add(intervals[0][1]);
        int rooms = 1;
        int taken = 1;
        
        for (int i = 1; i < intervals.length; i++) {
            int start = intervals[i][0];
            
            if (start >= ending.peek()) {
                ending.poll();
                taken--;
            }
            
            ending.add(intervals[i][1]);
            taken++;
            
            rooms = Math.max(rooms, taken);
            
        }
        
        return rooms;
    }
}

루션이 1% 참조
(concurrent 없애기 위한 방법으로만, comparator은 내가 만듬!!!) 후훗

Search 2D Matrix II

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        
        int h = matrix.length;
        int w = matrix[0].length;
        
        int x = 0;
        int y = matrix.length - 1;
        
        while (y >= 0 && x < w) {
            if (matrix[y][x] < target) {
                x++;
            } else if (matrix[y][x] > target) {
                y--;
            } else {
                return true;
            }
        }
        
        return false; 
        
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int h = matrix.length;
        int w = matrix[0].length;
        
        int x0 = 0;
        int y0 = h - 1;
        
        while (y0 >= 0 && x0 < w) {
            if (matrix[y0][x0] > target) {
                y0--;
            } else if (matrix[y0][x0] < target) {
                x0++;
            } else {
                return true; 
            }
        }
        
        return false; 
    }
}