Interval & range

Meeting room

simple question. just consider those intervals as a range with start and end point. Then, we should sort those intervals based on the start point. and check if there exists some kind of gap among them.

class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) return true;

        // sort the array according to the start time
        Arrays.sort(intervals, (a, b) -> (a.start - b.start));

        int end = intervals[0].end;
        for (int i = 1; i < intervals.length; ++i) {
            if (intervals[i].start < end) {
                return false;
            }
            end = intervals[i].end;
        }
        return true;
    }
}

Meeting room 2

the key to this problem is that we need to separate the intervals into two time points, which includes one isStart value and one time point.

class Solution {
    private class Point{
        int time;
        boolean isStart;

        public Point(int time, boolean isStart) {
            this.time = time;
            this.isStart = isStart;
        }
    }

    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) return 0;

        Point[] arr = new Point[intervals.length * 2];
        for (int i = 0; i < intervals.length; ++i) {
            arr[i * 2] = new Point(intervals[i].start, true);
            arr[i * 2 + 1] = new Point(intervals[i].end, false);
        }

        Arrays.sort(arr, (a, b) -> {
                // if a.isStart == true, means we need to deal with b first, 
                // reverse the a and b, which means I need to return 1;  b comes before a.

                if (a.time == b.time) return a.isStart ? 1 : -1;   
                else return a.time - b.time;
        });

        int maxOverlap = 0;
        int num = 0;
        for (int i = 0; i < arr.length; ++i) {
            if (arr[i].isStart) num++;
            else num--;
            maxOverlap = Math.max(maxOverlap, num);
        }

        return maxOverlap;
    }
}

follow up: how to get the most overlapped range?

  int maxOverLap = 0;
  int curCount = 0;
  int maxStart = 0;
  int maxEnd = 0;
  boolean found = false;
  for (Point pt : arr) {
      if (pt.isStart) {
        if (curCount > maxOverLap) {
          maxStart = pt.time;
          found = true;
        }
        curCount++;
      }
      else {
        if (found) {
          maxEnd = pt.time;
          found = false;
        }
        curCount--;
      }
  }

Merge Intervals

keep the start and end points along the way, and compare end points with start point of the next interval.

class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> list = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) return list;

        Collections.sort(intervals, (a, b) -> (a.start - b.start));

        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (int i = 1; i < intervals.size(); ++i) {
            if (end < intervals.get(i).start){
                list.add(new Interval(start, end));
                start = intervals.get(i).start;
                end = intervals.get(i).end;
            } else {
                end = Math.max(end, intervals.get(i).end);
            }
        }
        list.add(new Interval(start, end));
        return list;
    }
}

Range Addition

the key to this problem is puts inc at startIndex and -inc at endIndex + 1. To understand this method, we can start with one single update. refer to: [[[https://leetcode.com/problems/range-addition/discuss/84225/Detailed-explanation-if-you-don't-understand-especially-"put-negative-inc-at-endIndex+1"](https://leetcode.com/problems/range-addition/discuss/84225/Detailed-explanation-if-you-don't-understand-especially-"put-negative-inc-at-endIndex+1](https://leetcode.com/problems/range-addition/discuss/84225/Detailed-explanation-if-you-don't-understand-especially-"put-negative-inc-at-endIndex+1"](https://leetcode.com/problems/range-addition/discuss/84225/Detailed-explanation-if-you-don't-understand-especially-"put-negative-inc-at-endIndex+1)"](https://leetcode.com/problems/range-addition/discuss/84225/Detailed-explanation-if-you-don't-understand-especially-"put-negative-inc-at-endIndex+1"](https://leetcode.com/problems/range-addition/discuss/84225/Detailed-explanation-if-you-don't-understand-especially-"put-negative-inc-at-endIndex+1](https://leetcode.com/problems/range-addition/discuss/84225/Detailed-explanation-if-you-don't-understand-especially-"put-negative-inc-at-endIndex+1"](https://leetcode.com/problems/range-addition/discuss/84225/Detailed-explanation-if-you-don't-understand-especially-"put-negative-inc-at-endIndex+1)")\)

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        if (updates == null) return new int[0];

        int[] res = new int[length];
        int carry = 0;
        // add inc at startIndex, and -inc at endIndex
        for (int i = 0; i < updates.length; ++i) {
            int start = updates[i][0];
            int end = updates[i][1];
            int val = updates[i][2];

            res[start] += val;
            if (end == length - 1) carry -= val;
            else res[end + 1] -= val;
        }
        // second pass
        for (int i = 1; i < res.length; ++i) {
            res[i] += res[i - 1];
        }
        return res;
    }
}

Longest Consecutive Sequence

note that in this problem, we don't need consecutive numbers in original array. So actually we can sort those number firstly. One thing we need to notice is that there exists some duplicate numbers.

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        Arrays.sort(nums);

        int max = 1;
        int cur = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] == nums[i - 1]) continue;

            if (nums[i] == nums[i - 1] + 1) {
                cur++;
                max = Math.max(max, cur);
            } else {
                cur = 1;
            }
        }
        return max;
    }
}

the time complexity for the above algorithm is O(nlogN),

If we consider time interval to solve this problem, we can solve this in O(n) runtime. We only need to record the leftBound and rightBound. That's enough.

• Use a HashMap to store the length of the current range.
• For the given value, we can check the leftBound and rightBound, and put the length of new range into the map. What is leftBound? leftBound is the length of the given range that contains the current value.

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int n = nums.length;

        Map<Integer, Integer> map = new HashMap<>();
        int max = 1;
        for (int i = 0; i < n; ++i) {
            int cur = nums[i];
            if (map.containsKey(cur)) continue;

            int leftBound = map.containsKey(cur - 1) ? map.get(cur - 1) : 0;
            int rightBound = map.containsKey(cur + 1) ? map.get(cur + 1) : 0;

            // add the new entry to the map
            int sum = leftBound + rightBound + 1;
            max = Math.max(max, sum);
            map.put(cur, sum);

            // update the leftBound and rightBound value, that is leftmost and rightmost ranges
            if (leftBound != 0) map.put(cur - leftBound, sum);
            if (rightBound != 0) map.put(cur + rightBound, sum);
        }
        return max;
    }
}

Partition Ranges

class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> list = new ArrayList<>();
        if (S == null || S.length() == 0) return list;

        // record the last occurance index
        int[] arr = new int[26];
        for (int i = 0; i < S.length(); ++i) {
            arr[S.charAt(i) - 'a'] = i; 
        }

        int j = 0, base = 0;
        for (int i = 0; i < S.length(); ++i) {
            j = Math.max(j, arr[S.charAt(i) - 'a']);
            if (i == j) {
                list.add(i - base + 1);
                base = i + 1;
            }
        }
        return list;
    }
}