Interval Problems

**Questions**

Name | Example |
---|---|

Two ways to check whether two intervals overlap | min(y1, y2) > max(x1, x2); x1<y2 && x2>y1 |

Two types of intervals | `[x, y]` vs `[x, y)` |

Interval problems usually solved by heap or greedy algorithms | Leetcode: Car Pooling |

General idea of overlapping interval problems | Sort intervals, maintain an active set, loop each intervals |

Sort by point_x is common. But sometimes need to sort by point_y | Leetcode: Minimum Number of Arrows to Burst Balloons |

Typical problems: Interval conflict – Detect double booking | Leetcode: My Calendar I |

Typical problems: Interval conflict – Detect triple booking | Leetcode: My Calendar II |

Typical problems: Interval conflict – Detect K booking | Leetcode: My Calendar III, Leetcode: Car Pooling |

Typical problems: Interval List Intersections | Leetcode: Interval List Intersections |

Typical problems: Interval List Union | Leetcode: Insert Interval |

See all interval problems: #interval

- Review: Interval Problems
- LintCode: Time Intersection
- LintCode: Interval Search
- LintCode: Digital Coverage
- Leetcode: Teemo Attacking
- Leetcode: Smallest Range II
- Leetcode: Smallest Range I
- Leetcode: Non-overlapping Intervals
- Leetcode: My Calendar III
- Leetcode: My Calendar II
- Leetcode: My Calendar I
- Leetcode: Missing Ranges
- Leetcode: Minimum Number of Arrows to Burst Balloons
- Leetcode: Merge Intervals
- Leetcode: Meeting Rooms
- Leetcode: Insert Interval
- Leetcode: Find Right Interval
- Leetcode: Employee Free Time
- Leetcode: Car Pooling

See more blog_posts.