Greedy Schedule

Algorithms
greedy
Catalogue
  1. 1. Interval Schedule
    1. 1.1. 435. Non-overlapping Intervals
    2. 1.2. 252. Meeting Rooms
    3. 1.3. 253. Meeting Rooms II
  2. 2. Deadline Schedule
    1. 2.1. 630. Course Schedule III
  3. 3. Arrive
    1. 3.1. 55. Jump Game
    2. 3.2. 134. Gas Station

Interval Schedule

435. Non-overlapping Intervals

  • minimum number of removed intervels, maximum number of compatible intervals
  • sort by end time !!! Why?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        if not intervals: return 0

        intervals.sort(key = lambda x: x.end)
        cnt = 0
        prev_end = -float('inf')
        for inter in intervals:
            start, end = inter.start, inter.end
            if start >= prev_end:
                prev_end = end
            else:
                cnt += 1
        return cnt

252. Meeting Rooms

1
2
3
4
5
6
7
8
class Solution:
    def canAttendMeetings(self, intervals):
        intervals.sort(key = lambda x:x.end)

        for i in range(1, len(intervals)):
            if intervals[i].start < intervals[i-1].end:
                return False
        return True

253. Meeting Rooms II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def minMeetingRooms(self, intervals):
        times = []
        for inter in intervals:
            times.append((inter.start, 1))
            times.append((inter.end, 0))

        times.sort()
        cnt = 0
        res = 0
        for t, f in times:
            if f:
                cnt += 1
            else:
                cnt -= 1
            res = max(res, cnt)
        return res

Deadline Schedule

630. Course Schedule III

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def scheduleCourse(self, courses):
        start = 0
        heap = []
        for t, d in sorted(courses, key = lambda (t,d):d):
            start += t
            heapq.heappush(heap, -t)
            while start > d:
                start += heapq.heappop(heap)
        return len(heap)

Arrive

55. Jump Game

  • Use reach array will cause TLE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution(object):
        def canJump(self, nums):
            n = len(nums)
            reach = 0
            for i in xrange(n):
                if i > reach:
                    return False
                else:
                    reach = max(reach, i+nums[i])
            return reach >= n-1

134. Gas Station

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        if sum(cost) > sum(gas):
            return -1

        n = len(gas)
        balance = 0
        start = 0
        for i in range(n):
            balance += gas[i] - cost[i]
            if balance < 0:
                start = i + 1
                balance = 0
        return start
Share