Interval Scheduling

Input: set of intervals on the line, represented by pairs of points (ends of intervals).

Output: finding the largest set of intervals such that none two of them overlap.

Java
Time complexity: O(N log N)
Space complexity: O(N)

public class IntervalScheduling {

    static class Interval{
        private int start;
        private int finish;

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

        public int getStart(){
            return start;
        }

        public int getFinish(){
            return finish;
        }

        @Override
        public String toString(){
            return "[" + start + ", " + finish + "]";
        }
    }

    public List<Interval> maxNonOverlap(List<Interval> intervals){
        if (intervals == null || intervals.size() == 0){
            return Collections.EMPTY_LIST;
        }

        intervals.sort((Interval i1, Interval i2)->i1.getFinish() - i2.getFinish());

        List<Interval> res = new ArrayList<>();
        res.add(intervals.get(0));
        int ptr = 1;

        while (ptr < intervals.size()){
            Interval curr = res.get(res.size() - 1);
            while (ptr < intervals.size() && intervals.get(ptr).getStart() < curr.getFinish()){
                ++ptr;
            }
            if (ptr < intervals.size()){
                res.add(intervals.get(ptr++));
            }
        }

        return res;

    }

    public static void main(String[] args) {
        List<Interval> intervals = new ArrayList<>();
        intervals.add(new Interval(600, 830));
        intervals.add(new Interval(800, 900));
        intervals.add(new Interval(900, 1100));
        intervals.add(new Interval(900, 1130));
        intervals.add(new Interval(1030, 1400));
        intervals.add(new Interval(1230, 1400));

        List<Interval> nonOverlapIntervals = new IntervalScheduling().maxNonOverlap(intervals);
        System.out.println((Iterable) nonOverlapIntervals);

    }

}

Advertisements

Leetcode. Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

Java
Time complexity: O(N)
Space complexity: O(1)

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null || gas.length == 0){
            return -1;
        }
        
        int start = 0;
        int fuel = 0;
        int tank = 0;
        
        for (int i = 0; i < gas.length; ++i){
            fuel += gas[i] - cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0){ 
                tank = 0; start = i + 1; 
            } 
        } 
        return fuel >= 0 ? start : -1;
        
    }
}

Go
Time complexity: O(N)
Space complexity: O(1)

func canCompleteCircuit(gas []int, cost []int) int {
    if gas == nil || len(gas) == 0{
        return -1;
    }
    var fuel, tank, start int = 0, 0, 0
    
    for i := 0; i < len(gas); i++ {
        fuel += gas[i] - cost[i]
        tank += gas[i] - cost[i]
        if tank < 0{
            tank = 0
            start = i + 1
        }
    }
    
    if fuel < 0{
        return -1
    } else{
        return start;
    }
}