Changing TreeMap to PriorityQueue reduced runtime by 10ms [ Java]
This is one of the good examples to understand scenarios where queue would perform better vs treeMap.\n- TreeMap always maintains the sort order in insertions a
This is one of the good examples to understand scenarios where queue would perform better vs treeMap.\n- TreeMap always maintains the sort order in insertions and deletions. Hence for every insertion and deletion, the time required would be O(logn) \n- Whereas priority queue only maintains heap property (max heap or min heap)\n\nHence in cases when we have lot of insertions and deletions, queue works better than heap.\n```\nclass ExamRoom {\n\n    static Queue<Interval> map;\n    static int len;\n\n    public ExamRoom(int N) {\n       map =  new PriorityQueue<>(10,new TreeComparator());\n       len = N-1;\n    }\n    \n    public int seat() {\n         if (map.isEmpty()) {\n            map.add(new Interval(0, -1));\n            return 0;\n        }\n        Interval interval = map.poll();\n        int index;\n        if (interval.start == -1) {\n            index = 0;\n            map.add(new Interval(0, interval.end));\n        } else if (interval.end == -1) {\n            index = len;\n            map.add(new Interval(interval.start, len));\n        } else {\n            index = (interval.start + interval.end) / 2;\n            map.add(new Interval(index, interval.end));\n            map.add(new Interval(interval.start, index));\n        }\n        return index;\n    }\n    \n    public void leave(int index) {\n       Interval startInterval = new Interval();\n        Interval endInterval = new Interval();\n\n        for ( Interval interval : map) {\n            if (interval.start == index) {\n                startInterval = interval;\n            }\n            if (interval.end == index) {\n                endInterval = interval;\n            }\n        }\n        if (index == 0) {\n            map.remove(startInterval);\n            map.add(new Interval(-1,startInterval.end));\n\n        } else if (index == len) {\n            map.remove(endInterval);\n            map.add(new Interval(endInterval.start,-1));\n        } else {\n            map.remove(startInterval);\n            map.remove(endInterval);\n            map.add(new Interval(endInterval.start, startInterval.end));\n        }\n}\n    \n    public int getDifference(int start,int end){\n        if(start == -1)\n            return end;\n        else if(end == -1)\n            return len - start;\n        else\n            return (end - start) / 2;\n    }\n\n  class TreeComparator implements Comparator<Interval> {\n\n        @Override\n        public int compare(Interval o1, Interval o2) {\n            int diffFirst = getDifference(o1.start,o1.end);\n            int diffSecond = getDifference(o2.start,o2.end);\n            return (diffFirst == diffSecond) ? (o1.start + diffFirst) - (o2.start + diffSecond) : diffSecond - diffFirst;\n\n        }\n    }\n\n    class Interval {\n        int start;\n        int end;\n\n        Interval(int start, int end) {\n            this.start = start;\n            this.end = end;\n        }\n\n        public Interval() {\n\n        }\n\n        @Override\n        public String toString() {\n            return this.start + " " + this.end;\n        }\n    }\n    \n}\n```\n
[]