You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

 public int[][] insert(int[][] intervals, int[] newInterval) {
      
        List<int[]> res = new ArrayList<>();
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            res.add(intervals[i]);
            i++;
        }
        
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        
        res.add(newInterval);
         while (i < intervals.length) {
            res.add(intervals[i]);
            i++;
        }
        
        
        return res.toArray(new int[res.size()][]);
    }

public class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> res = new ArrayList<>();
        
        List<int[]> list = new ArrayList<>();
        for (List<Interval> intervals : schedule) {
            for (Interval interval : intervals) {
                list.add(new int[]{interval.start, 0});
                list.add(new int[]{interval.end, 1});
            }
        }
        
        list.sort((p1, p2) -> p1[0] != p2[0] ? Integer.compare(p1[0], p2[0]) : Integer.compare(p1[1], p2[1]));
        int count = 0;
        boolean begin = false;
        for (int[] pair : list) {
            if (pair[1] == 0) {
                count++;
            } else {
                count--;
            }
            
            if (count == 0) {
                res.add(new Interval(pair[0], pair[0]));
                begin = true;
            } else if (begin) {
                res.get(res.size() - 1).end = pair[0];
                begin = false;
            }
        }
        
        res.remove(res.size() - 1);
        return res;
    }
}

class Interval {
    public int start;
    public int end;
    
    public Interval() {
    }
    
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[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:

Constraints:

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

public int[][] merge(int[][] intervals) {
        
        if (intervals == null || intervals.length == 0) {
            return intervals;
        }
        
        Arrays.sort(intervals, (int[]a, int[]b) -> a[0] - b[0]);
        
    
        
        
        List<int[]> res = new ArrayList<>();
        
        res.add(intervals[0]); // [1, 3] ->
        
        for (int i = 1; i < intervals.length; i++) { // start from 1
            int[] end = res.get(res.size() - 1); // end = [1, 3] vs intervals[1][0]
            if (end[1] >= intervals[i][0]) { // 3 > 2
                end[1] = Math.max(end[1], intervals[i][1]); // end = [1, 6]
            } else {
                res.add(intervals[i]);
            }  
        }
        return res.toArray(new int[res.size()][2]);    
    }

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]:

lefti is the x coordinate of the left edge of the ith building.
righti is the x coordinate of the right edge of the ith building.
heighti is the height of the ith building.
You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3],[4 5],[7 5],[11 5],[12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...,[2 3],[4 5],[12 7],...]


Example 1:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

 public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> res = new ArrayList<>();
        /*
        [L, R, H]   -> [L, R]       [R, H]
        [[2,9,10],      [2,-10],    [9,10]
        [3,7,15],       [3,-15],    [7,15] 
        [5,12,12],      [5,-12],    [12,12]
        [15,20,10],
        [19,24,8]]
        
        用正负区分是左端点还是右端点
        然后排列他们, 但是高度是按降序排列处理
        [2,-10],
        [3,-15],
        [5,-12],
         [7,15]
         [9,10]
        */
        List<int[]> buildLines = new ArrayList<>();
        
        for (int[] points : buildings) {
            buildLines.add(new int[]{points[0], -points[2]});
            buildLines.add(new int[]{points[1], points[2]});
        }
        
        Collections.sort(buildLines, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        });
        
        PriorityQueue<Integer> maxHeap = new  PriorityQueue<>((a, b) -> b - a);
        maxHeap.add(0);
        int preHightest = 0;
        
        for (int[] points : buildLines) {
            if (points[1] < 0) {    // h[1] < 0, that means it meets a new building, so add it to pq
                maxHeap.add(-points[1]);
            } else {
                maxHeap.remove(points[1]); // h[1] >=0, that means it has reached the end of the building, so remove it from pq
            }
            // the current max height in all encountered buildings
            int curHeight = maxHeap.peek();
             // if the max height is different from the previous one, that means a critical point is met, add to result list
            if (curHeight != preHightest) {
                res.add(Arrays.asList(points[0], curHeight));
                preHightest = curHeight;
            }
        }
        
        return res;
    }

 public List<List<Integer>> getSkyline(int[][] buildings) {
     return merge(buildings, 0, buildings.length - 1);
 }

 private LinkedList<int[]> merge(int[] buildings, int lo, int hi) {
     LinkedList<int[]> res = new LinkedList<>();
     if (lo > hi) {
        return res;
     } else if (lo == hi) {
         res.add(new int[]{buildings[lo][0], buildings[lo][2]}); //  [[x, h], [y, 0]]
         res.add(new int[]{buildings[lo][1], 0});
         return res;
     }

     int mid = lo + (hi - lo)/2;
     LinkedList<int[]> left = merge(buildings, lo, mid); // left: [[0, 3], [2, 0]] 
    LinkedList<int[]> right = merge(buildings, mid + 1, hi); // right: [[2, 3], [5, 0]]
    int leftH = 0, rightH = 0;
        while(!left.isEmpty() || !right.isEmpty()) {
            long x1 = left.isEmpty()? Long.MAX_VALUE: left.peekFirst()[0]; // 0
            long x2 = right.isEmpty()? Long.MAX_VALUE: right.peekFirst()[0]; // 2
            int x = 0;
            if(x1 < x2) {
                int[] temp = left.pollFirst();  // [0, 3]
                x = temp[0]; // 0
                leftH = temp[1]; // 3
            } else if(x1 > x2) {
                int[] temp = right.pollFirst();
                x = temp[0];
                rightH = temp[1];
            } else {
                x = left.peekFirst()[0];
                leftH = left.pollFirst()[1];
                rightH = right.pollFirst()[1];
            }
            int h = Math.max(leftH, rightH);    // 3
            if(res.isEmpty() || h != res.peekLast()[1]) {
                res.add(new int[]{x, h}); // [0, 3]
            }
        }
        return res;
    }
 

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

 

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals == null || intervals.length == 0) return 0; 
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        
        int end = intervals[0][1]; 
        int count = 1; 
        
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] >= end){
                end = intervals[i][1]; 
                count++; 
            }
        }
        
        return intervals.length - count; 
    }

    //  int end = Integer.MIN_VALUE;
    //     int count = 0;
    //     for (Interval interval : intervals) {
    //         if (interval.start >= end) end = interval.end;
    //         else count++;
    //     }

    //     return count;
    // }

      public int eraseOverlapIntervals(int[][] intervals) {
        [[1,100],[11,22],[1,11],[2,12]]
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]); //[1,11],[2,12], [11,22], [1,100]
        
        
        int end = intervals[0][1];
        int len = 1;
        
        
       
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= end) { // 将 11 与2， 22，数组[0]z对比
                end = intervals[i][1];
                len++;
            }
        }
        return intervals.length - len;
    }
}
public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int prevEnd = intervals[0][1];
        int count = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (prevEnd > intervals[i][0]) {
                count++;
                prevEnd = Math.min(intervals[i][1], prevEnd); // 把 11 和100 取最小的
            } else {
                prevEnd = intervals[i][1];
            }
        }
        return count;
    }

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

 

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

 public int findMinArrowShots(int[][] points) {
        int count = 1;
        Arrays.sort(points, (a, b) -> Integer.compare(a[0],b[0]));
        int tmp = points[0][1]; // 6
        for (int i = 1; i < points.length; i++) {
            if (tmp < points[i][0]) {
                count++;
                tmp = points[i][1];
            } 
        }
        return count;
 }

  public int findMinArrowShots(int[][] points) {
        int count = 1;
        Arrays.sort(points, (a, b) -> Integer.compare(a[1],b[1]));
        int tmp = points[0][1]; // 6
        for (int i = 1; i < points.length; i++) {
            if (tmp < points[i][0]) {
                count++;
                tmp = points[i][1];
            } 
        }
        return count;
    }

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

MyCalendar() Initializes the calendar object.
boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.
 

Example 1:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

 public boolean book(int start, int end) {
        if (res.size() == 0) {
            res.add(new int[]{start, end});
            return true;
        }
        int[] tmp = res.get(res.size() - 1);
        
        if (Math.max(tmp[0], start) < Math.min(tmp[1], end)) {
            return false;
        }
        
        res.add(new int[]{start, end});
        return true;
        
        
       
    }

     res = new ArrayList<>();
    }
    
    public boolean book(int start, int end) {
       
        for (int[] tmp : res) {
             if (Math.max(tmp[0], start) < Math.min(tmp[1], end)) {
            return false;
        }
        }
       
        
        res.add(new int[]{start, end});
        return true;
                  
    }

     public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> lowerEntry = map.lowerEntry(end); // start1 == end will not be seen as overlap
        if(lowerEntry != null && lowerEntry.getValue() > start) { // or use or the condition as authors posts
            return false;
        }
     
        map.put(start, end);
        return true;
    }

ou are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.

A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendarTwo class:

MyCalendarTwo() Initializes the calendar object.
boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.
 

Example 1:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

class MyCalendarTwo {

  
        List<int[]> books = new ArrayList<>();
    
    
    public boolean book(int start, int end) {
        
       MyCalendar overlaps = new MyCalendar();
        for (int[] b : books)
            if (Math.max(b[0], start) < Math.min(b[1], end)) // overlap exist
                if (!overlaps.book(Math.max(b[0], start), Math.min(b[1], end))) return false; // overlaps overlapped
        books.add(new int[]{ start, end });
        return true;
    }
    
     private static class MyCalendar {
        List<int[]> books = new ArrayList<>();
        public boolean book(int start, int end) {
            for (int[] b : books)
                if (Math.max(b[0], start) < Math.min(b[1], end)) return false;
            books.add(new int[]{ start, end });
            return true;
        }
    }
}

class MyCalendarTwo {

    private TreeMap<Integer, Integer> map;
    
    class MyCalendarTwo() {
        map = new TreeMap<>();
    }

    
    public boolean book(int start, int end) {
        
        map.put(start, map.getOrDefault(start, 0) + 1);
        map.put(end, map.getOrDefault(end, 0) - 1);
        int count = 0;

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            count += entry.getValue();
            if (count > 3) {
                // 取消这次行程
                map.put(start, map.getOrDefault(start, 0) - 1);
               
                if (map.get(start) == 0) {
                    map.remove(start);
                }
                map.put(end, map.getOrDefault(end, 0) + 1);
                 if (map.get(end) == 0) {
                    map.remove(end);
                }
                return false;
                //  ConcurrentModificationException is thrown when the iterator checks the size of the map in method "iterator.hasNext()" 因为这里直接return 了
                //所以没有抛出错误
            }
        }
        return true;
    }
}

public int minMeetingRooms(List<Interval> intervals) {
        if (intervals.isEmpty() || intervals.size() == 1) return intervals.size();
        Collections.sort(intervals, (a, b) -> a.start - b.start);
 
        // 小根堆，存储会议，出堆按照结束会议的最早时间
        PriorityQueue<Interval> minHeap = new PriorityQueue<>((a, b) -> a.end - b.end);
        minHeap.offer(intervals.get(0));
 
        for (int i = 1; i < intervals.size(); i++) {
            Interval prev = minHeap.poll();
            Interval curr = intervals.get(i);
            if (curr.start >= prev.end) {
                // 没有交叉，可以分配到同一个时间，将end时间延长
                prev.end = Math.max(prev.end, curr.end);
            } else { // 交叉，offer当前的时间间隔
                minHeap.offer(curr);
            }
            minHeap.offer(prev);
        }
        return minHeap.size();
    }

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)

You are given some events [start, end), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarThree class:

MyCalendarThree() Initializes the object.
int book(int start, int end) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.
 

Example 1:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

There is a long and thin painting that can be represented by a number line. The painting was painted with multiple overlapping segments where each segment was painted with a unique color. You are given a 2D integer array segments, where segments[i] = [starti, endi, colori] represents the half-closed segment [starti, endi) with colori as the color.

The colors in the overlapping segments of the painting were mixed when it was painted. When two or more colors mix, they form a new color that can be represented as a set of mixed colors.

For example, if colors 2, 4, and 6 are mixed, then the resulting mixed color is {2,4,6}.
For the sake of simplicity, you should only output the sum of the elements in the set rather than the full set.

You want to describe the painting with the minimum number of non-overlapping half-closed segments of these mixed colors. These segments can be represented by the 2D array painting where painting[j] = [leftj, rightj, mixj] describes a half-closed segment [leftj, rightj) with the mixed color sum of mixj.

For example, the painting created with segments = [[1,4,5],[1,7,7]] can be described by painting = [[1,4,12],[4,7,7]] because:
[1,4) is colored {5,7} (with a sum of 12) from both the first and second segments.
[4,7) is colored {7} from only the second segment.
Return the 2D array painting describing the finished painting (excluding any parts that are not painted). You may return the segments in any order.

A half-closed segment [a, b) is the section of the number line between points a and b including point a and not including point b.

Example 1:

Input: segments = [[1,4,5],[4,7,7],[1,7,9]]
Output: [[1,4,14],[4,7,16]]
Explanation: The painting can be described as follows:
- [1,4) is colored {5,9} (with a sum of 14) from the first and third segments.
- [4,7) is colored {7,9} (with a sum of 16) from the second and third segments.

public List<List<Long>> splitPainting(int[][] segments) {
	TreeMap<Integer, Long> map = new TreeMap<>();

	for(int segment[]: segments) {
		map.put(segment[0], map.getOrDefault(segment[0], 0L) + segment[2]);
		map.put(segment[1], map.getOrDefault(segment[1], 0L) - segment[2]);
	}

	List<List<Long>> result = new ArrayList<>();

	int prev = 0;
	long sum = 0;

	for(int key: map.keySet()) {
		if(sum != 0) { // Ignore the unpainted interval
			result.add(Arrays.asList((long)prev, (long)key, sum)); // Add the interval
		}

		sum += map.get(key);
		prev = key;
	}

	return result;
}

There are several squares being dropped onto the X-axis of a 2D plane.

You are given a 2D integer array positions where positions[i] = [lefti, sideLengthi] represents the ith square with a side length of sideLengthi that is dropped with its left edge aligned with X-coordinate lefti.

Each square is dropped one at a time from a height above any landed squares. It then falls downward (negative Y direction) until it either lands on the top side of another square or on the X-axis. A square brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in place and cannot be moved.

After each square is dropped, you must record the height of the current tallest stack of squares.

Return an integer array ans where ans[i] represents the height described above after dropping the ith square.

 

Example 1:


Input: positions = [[1,2],[2,3],[6,1]]
Output: [2,5,5]
Explanation:
After the first drop, the tallest stack is square 1 with a height of 2.
After the second drop, the tallest stack is squares 1 and 2 with a height of 5.
After the third drop, the tallest stack is still squares 1 and 2 with a height of 5.
Thus, we return an answer of [2, 5, 5].

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

 

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.