8.19刷题

第一题 57. Insert Interval

题目描述

假定现在给定一些间距(Intervals)，要求他们是不重复的且是按照顺序的，求插入一个间距后(Interval)，形成的新的间距样式

算法

思路较为清晰，如果interval.end < newInterval.start说明其肯定在newInterval之前，按照原来的形式进行插入

当interval.end > newInterval.start的时候，说明新的头已经出现，新的头的大小事Math.min(interval.start, newInterval.start)。

新的尾的结束点是在interval.start > newInterval.end的时候，之后仍然按照正常顺序进行插入操作

class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> res = new ArrayList<>();
        
        int i = 0;
        for (; i < intervals.size(); i++) {
            Interval interval = intervals.get(i);
            if (interval.end < newInterval.start)
                res.add(new Interval(interval.start, interval.end));
            else
                break;
        }

        for (; i < intervals.size(); i++) {
            Interval interval = intervals.get(i);
            if (interval.start > newInterval.end)
                break;
            newInterval = new Interval(
                    Math.min(newInterval.start, interval.start),
                    Math.max(newInterval.end, interval.end)
            );
        }
        res.add(newInterval);
        
        for(; i < intervals.size(); i++) {
            Interval interval = intervals.get(i);
            res.add(interval);
        }
        return res;        
    }
}

相关题目

56. Merge Intervals

合并无序的intervals

核心算法，首先排序，然后确定头尾，进行合并。

第二题 252. Meeting Rooms

题目描述

给定一个开始和结束的时间段，查看某个人能否参加所有的会议

算法

class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        if (intervals.length == 0)
            return true;
        
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval obj1, Interval obj2) {
                return obj1.start - obj2.start;
            } 
        });
        
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < intervals[i - 1].end)
                return false;
        }
        return true;
    }
}

第三题 253. Meeting Rooms II

题目描述

现在仍然与上一题一样，不过现在需要求解的是需要同时排多少个教室，才能够满足所给出的时间间隔的需求。

算法

这道题目，思考的本质是在同一个重复的时间段内，究竟多少个叠加的Interval。我们必须首先将Intervals进行排序，获得所有的开始和结束的时间，然后再对交叉的时间进行统计

Min Heap

主要思路是:

如果新的start大于之前最小的end那么肯定需要一个新教室

否则，我们将之前那间的结束时间延展到新的最小的这个结束时间

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

        Arrays.sort(intervals, new Comparator<Interval> (){
            @Override
            public int compare(Interval obj1, Interval obj2) {
                return obj1.start - obj2.start;
            }
        });

        PriorityQueue<Interval> pq = new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>() {
            @Override
            public int compare(Interval obj1, Interval obj2) {
                return obj1.end - obj2.end;
            }
        });

        pq.offer(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            Interval interval = intervals[i];
            Interval cur = pq.poll();

            //if the new meet start time begins after the last one meeting end
            //then we just extend the end time to new end time
            if (interval.start >= cur.end) {
                cur.end = interval.end;
            }
            //we need one more room now
            else {
                pq.offer(interval);
            }
            pq.offer(cur);
        }
        return pq.size();
    }
}

Arrays

思路与之前一样，只是我们现在统计最多有几个starts是在某个ends之前的

class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals.length == 0)
            return 0;
        int[] starts = new int[intervals.length], ends = new int[intervals.length];
        for (int i = 0; i < starts.length; i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        
        Arrays.sort(starts);
        Arrays.sort(ends);
        
        int notEnd = 0; //Meeting room not end before a new meeting
        for (int i = 0; i < starts.length; i++) {
            if (starts[i] >= ends[notEnd])
                notEnd++;
        }
        return starts.length - notEnd;
    }
}