Interval Array 04.09.2022

Coding keep your coding sharp
1 
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:

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

Is it for me?

Are you an engineering manager who wants to keep your coding skills sharp?
Are you Software engineer who wants to move sometime in 1+ years?

If you answered YES to any of the questions - You have come to the right place.

How to Join Us

Join us and practice coding
Every Saturday 11:00 am pst

**To JOIN just click

Saturday, April 9 · 6:00 – 7:00pm PST
Google Meet joining info
Video call link: https://meet.google.com/hfg-mnuc-yeb

#systemdesign #interview #softwareengineering #facebook #google #amazon #computerscience #algorithms #datastructures

2

class Solution {
public int[][] merge(int[][] intervals) {

    Arrays.sort(intervals, new Comparator<int[]>() {
        @Override
        public int compare(int[] first, int[] second)
        {
            return Integer.compare(first[0], second[0]);
        }
    });
    
    List<int[]> resultList = new ArrayList<int[]>();
    for (int[] itv : intervals)
    {
        int[] last = resultList.size() == 0 ? null : resultList.get(resultList.size()-1);
        if (last == null || last[1] < itv[0])
            resultList.add(itv);
        else
            last[1] = Math.max(last[1], itv[1]);
    }
    
    return resultList.stream().toArray(int[][] ::new);
}

}

Time Complexity : O(n log n). due to the sort
Space Complexity ; O(n)

Thanks in advance for improvements and alternatives !