Interval - Algorithm

When to use interval
- Sort by start or end first
- Kind of Greedy
- sort interval, then binary search (LeetCode 436 - Find Right Interval)
  -- Sort Interval
  -- Or sort start, end separately
  -- Or sort start, end at one array
- Use TreeMap or TreeMap> to store intervals and compare based on start
- Use Priorityqueue
- Sweep line algorithm
- Interval operation: insert, merge interval

X. Interval Binary Search Tree
- How to remove an interval
private class Node {
 Interval interval; // or directly store start, end; start is used as the key to build BST
 Node left, right;
 int maxValue; // the max value of all intervals rooted in this node
}

Unlimited switches
isToggled(long idx)
toggle(long start, long end)

Sort by start
Given n appointments, find all conflicting appointments

LeetCode 616 - Add Bold Tag in String

LettCode 452 - Minimum Number of Arrows to Burst Balloons

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

LeetCode 436 - Find Right Interval
Sort by start then binary search

Google – Remove Alarm
Google – Find a Path Among Circles
- Only merge interval when two circles intersects

LeetCode 352 - Data Stream as Disjoint Intervals
Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.
TreeMap intervals to merge interval based on start
TreeSet

LeetCode 436 - Find Right Interval
Use TreeMap to store intervals
- Use TreeMap> to handle duplicate start
Sort Intervals based on start + binary search

LeetCode 253 - Meeting Rooms II
find the minimum number of conference rooms required.
starts[i] = intervals[i].start;
ends[i] = intervals[i].end;
Arrays.sort(starts);
Arrays.sort(ends);
- Use PriorityQueue
Arrays.sort(intervals, (a, b) -> { return a.start - b.start;}});
PriorityQueue ends = new PriorityQueue();
ends.offer(intervals[0].end);
https://discuss.leetcode.com/topic/25503/java-another-thinking-process-event-queue/2
pq.offer(new Event(interval.start, 1));
pq.offer(new Event(interval.end, 0));

LeetCode 252 - Meeting Rooms
determine if a person could attend all meetings.

LeetCode 56 - Merge Intervals
LeetCode 57 - Insert Interval

LeetCode 218 - The Skyline Problem
Using TreeMap
https://discuss.leetcode.com/topic/22482/short-java-solution
http://www.programcreek.com/2014/06/leetcode-the-skyline-problem-java/
https://discuss.leetcode.com/topic/28482/once-for-all-explanation-with-clean-java-code-o-n-2-time-o-n-space
https://discuss.leetcode.com/topic/38065/java-solution-using-priority-queue-and-sweepline
Sweepline is used in solving the problem. List height is used to save each of the line segments including both start and end point. The trick here is to set the start segment as negative height. This has a few good uses:
first, make sure the start segment comes before the end one after sorting.
second, when pushing into the queue, it is very each to distinguish either to add or remove a segment.
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> heights = new ArrayList<>();
        for (int[] b: buildings) {
            heights.add(new int[]{b[0], - b[2]});
            heights.add(new int[]{b[1], b[2]});
        }
        Collections.sort(heights, (a, b) -> (a[0] == b[0]) ? a[1] - b[1] : a[0] - b[0]);
        TreeMap heightMap = new TreeMap<>(Collections.reverseOrder());
        heightMap.put(0,1);
        int prevHeight = 0;
        List<int[]> skyLine = new LinkedList<>();
        for (int[] h: heights) {
            if (h[1] < 0) {
                Integer cnt = heightMap.get(-h[1]);
                cnt = ( cnt == null ) ? 1 : cnt + 1;
                heightMap.put(-h[1], cnt);
            } else {
                Integer cnt = heightMap.get(h[1]);
                if (cnt == 1) {
                    heightMap.remove(h[1]);
                } else {
                    heightMap.put(h[1], cnt - 1);
                }
            }
            int currHeight = heightMap.firstKey();
            if (prevHeight != currHeight) {
                skyLine.add(new int[]{h[0], currHeight});
                prevHeight = currHeight;
            }
        }
        return skyLine;
    }
X. Divide and Conquer
https://discuss.leetcode.com/topic/16511/share-my-divide-and-conquer-java-solution-464-ms
http://www.geeksforgeeks.org/divide-and-conquer-set-7-the-skyline-problem/
 public List<int[]> getSkyline(int[][] buildings) {
  if (buildings.length == 0)
   return new LinkedList<int[]>();
  return recurSkyline(buildings, 0, buildings.length - 1);
 }

 private LinkedList<int[]> recurSkyline(int[][] buildings, int p, int q) {
  if (p < q) {
   int mid = p + (q - p) / 2;
   return merge(recurSkyline(buildings, p, mid),
     recurSkyline(buildings, mid + 1, q));
  } else {
   LinkedList<int[]> rs = new LinkedList<int[]>();
   rs.add(new int[] { buildings[p][0], buildings[p][2] });
   rs.add(new int[] { buildings[p][1], 0 });
   return rs;
  }
 }

 private LinkedList<int[]> merge(LinkedList<int[]> l1, LinkedList<int[]> l2) {
  LinkedList<int[]> rs = new LinkedList<int[]>();
  int h1 = 0, h2 = 0;
  while (l1.size() > 0 && l2.size() > 0) {
   int x = 0, h = 0;
   if (l1.getFirst()[0] < l2.getFirst()[0]) {
    x = l1.getFirst()[0];
    h1 = l1.getFirst()[1];
    h = Math.max(h1, h2);
    l1.removeFirst();
   } else if (l1.getFirst()[0] > l2.getFirst()[0]) {
    x = l2.getFirst()[0];
    h2 = l2.getFirst()[1];
    h = Math.max(h1, h2);
    l2.removeFirst();
   } else {
    x = l1.getFirst()[0];
    h1 = l1.getFirst()[1];
    h2 = l2.getFirst()[1];
    h = Math.max(h1, h2);
    l1.removeFirst();
    l2.removeFirst();
   }
   if (rs.size() == 0 || h != rs.getLast()[1]) {
    rs.add(new int[] { x, h });
   }
  }
  rs.addAll(l1);
  rs.addAll(l2);
  return rs;
 }

X. Thought as different kinds of evet: start/end event
LeetCode 253 - Meeting Rooms II
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
https://discuss.leetcode.com/topic/35253/explanation-of-super-easy-java-solution-beats-98-8-from-pinkfloyda
    public int minMeetingRooms(Interval[] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];
        for(int i=0; iint
rooms = 0int endsItr = 0for(int i=0; iif(starts[i]else endsItr++; } return rooms; }X. Using prority queue + sweep line
http://www.cnblogs.com/yrbbest/p/5012534.html
https://discuss.leetcode.com/topic/20958/ac-java-solution-using-min-heap/10
    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0)
            return 0;
        
        Arrays.sort(intervals, new Comparator() {
            public int compare(Interval t1, Interval t2) {
                if(t1.start != t2.start)
                    return t1.start - t2.start;
                else
                    return t1.end - t2.end;
            }
        });
        
        int maxOverlappingMeetings = 0;
        PriorityQueue pq = new PriorityQueue<>();      // min oriented priority queue
        
        for(int i = 0; i < intervals.length; i++) {         // sweeping-line algorithms
            pq.add(intervals[i].end);
            while(pq.size() > 0 && intervals[i].start >= pq.peek())
                pq.remove();
                
            maxOverlappingMeetings = Math.max(maxOverlappingMeetings, pq.size());
        }
        
        return maxOverlappingMeetings;
    }
https://discuss.leetcode.com/topic/25503/java-another-thinking-process-event-queue/


LeetCode 252 - Meeting Rooms
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.
https://discuss.leetcode.com/topic/31306/easy-java-solution-beat-98
https://discuss.leetcode.com/topic/20959/ac-clean-java-solution
public boolean canAttendMeetings(Interval[] intervals) {
  if (intervals == null)
    return false;

  // Sort the intervals by start time
  Arrays.sort(intervals, new Comparator() {
    public int compare(Interval a, Interval b) { return a.start - b.start; }
  });
  
  for (int i = 1; i < intervals.length; i++)
    if (intervals[i].start < intervals[i - 1].end)
      return false;
  
  return true;
}

Post a Comment

Labels

Java (159) Lucene-Solr (111) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (37) Eclipse (33) Code Example (31) Linux (24) JavaScript (23) Spring (22) Windows (22) Web Development (20) Nutch2 (18) Tools (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (13) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) Problem Solving (9) UIMA (9) html (9) Http Client (8) Maven (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) Lesson Learned (5) Programmer Skills (5) System Design (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts