Greedy no, Greedy yes


  • 0
    D

    I have thought two greedy solutions. The first one fails, and the second one works. So this post actually expresses my long time confusion about greedy method, because greedy method is more like an explanation after we know the algorithm works instead of a thinking guideline to solve a new problem. "It's easy to be wise after the event."

    The lesson I learned is that greedy is not a guideline of thinking a solution, you still need to find the provable insight.

    The failed greedy method treats the problem as a graph. Vertex represents interval, and edge represents conflicts between two intervals. Then the problem becomes: deleting minimum amount of vertices (and incident edges) such that there is no edge (no conflict). My greedy method is: always pick the vertex that has the largest degree in graph (undirected). The failed test case is: [[0,2],[1,3],[1,3],[2,4],[3,5],[3,5],[4,6]].

    The failed greedy method code is:

    public class Solution {
        public int eraseOverlapIntervals(Interval[] intervals) {
            if (intervals == null || intervals.length <= 1) {
                return 0;
            }
            int n = intervals.length;
            GraphNode[] graph = new GraphNode[n];
            for (int i = 0; i < n; i++) {
                graph[i] = new GraphNode(i);
            }
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    GraphNode nodei = graph[i];
                    GraphNode nodej = graph[j];
                    if (overlap(intervals[nodei.id], intervals[nodej.id])) {
                        nodei.neighbors.add(j);
                        nodej.neighbors.add(i);
                    }
                }
            }
            int erase = 0;
            for (int t = 0; t < n; t++) {
                if (eraseMaxDegree(graph)) {
                    erase++;
                } else {
                    break;
                }
            }
            return erase;
        }
    
        private boolean overlap(Interval i1, Interval i2) {
            return !(i1.end <= i2.start || i1.start >= i2.end);
        }
    
        private boolean eraseMaxDegree(GraphNode[] graph) {
            int maxdegree = 0;
            int index = -1;
            for (int i = 0; i < graph.length; i++) {
                if (graph[i] == null) {
                    continue;
                }
                if (graph[i].neighbors.size() > maxdegree) {
                    maxdegree = graph[i].neighbors.size();
                    index = i;
                }
            }
            if (maxdegree == 0) {
                return false;
            }
            for (int neighbor : graph[index].neighbors) {
                graph[neighbor].neighbors.remove(graph[index].id);
            }
            graph[index] = null;
            return true;
        }
    
        class GraphNode {
            int id;
            Set<Integer> neighbors = new HashSet<>();
    
            GraphNode(int id) {
                this.id = id;
            }
        }
    }
    
    

    The second greedy method sorts the intervals by starting point. Then scan the whole array. We maintain an interval list that has non-conflicting intervals. Whenever a new interval conflicts with the tail interval of the list, we need to kick one of them out. We always pick the interval that has the larger end point.

    The second greedy method code:

    public class Solution {
        public int eraseOverlapIntervals(Interval[] intervals) {
            if (intervals == null || intervals.length <= 1) {
                return 0;
            }
            Arrays.sort(intervals, new Comparator<Interval>() {
                @Override
                public int compare(Interval i1, Interval i2) {
                    return i1.start - i2.start;
                }
            });
            List<Interval> list = new ArrayList<>();
            for (int i = 0; i < intervals.length; i++) {
                if (list.size() == 0) {
                    list.add(intervals[i]);
                } else if (intervals[i].start < list.get(list.size() - 1).end) {
                    list.set(list.size() - 1, intervals[i].end < list.get(list.size() - 1).end ? intervals[i] : list.get(list.size() - 1));
                } else {
                    list.add(intervals[i]);
                }
            }
            return intervals.length - list.size();
        }
    }
    

  • 0
    Y
    This post is deleted!

  • 0
    D

    @yixuanwang.start Proof beats intuition, haha :) I have given one test case that my first greedy method failed. [2,4] will be chosen by algorithm, however, it should stay.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.