Day 22 of 30 days of Data Structures and Algorithms and System Design Simplified — Intervals
Welcome back peeps. Hope all’s well. In this post we will cover Intervals technique as follows —
What and Why Intervals Technique(in 2–3 sentences)?
How does Intervals work?
Important Patterns and Techniques in Intervals Questions
Most Important Questions with Solutions
Tips and Techniques to solve Intervals Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Intervals
Importance : High
Note : New Intervals questions with solutions are added every day. So keep checking this post daily.
Let’s dive in!
What is Intervals?
Interval is a technique applied to the set of array question where an array/list of time is given ( that form an interval) and the values represent the start and the end value of the give time interval/frame.
Examples of Intervals problems —
Meeting Rooms
Calendar and Employee time
Exam Room
Events and Attendance
Merge Intervals
Insert Intervals etc
How does Intervals work?
Interval techniques are methods used to represent and manipulate sets of continuous ranges or intervals of values. These techniques are commonly used in fields such as computer science, mathematics, and statistics, to represent and work with ranges of values, such as dates, times, or numerical ranges.
Interval techniques involve operations such as creating, merging, and querying intervals, and are implemented using data structures such as interval trees or segment trees.
Intervals depend on the start and the end time.
Before attempting the interval question, sort the intervals list ( by start or the end times)
Edge cases —
- Single interval ( Only A interval is there)
- Two intervals (A and B intervals overlap)
- Non-overlapping intervals (A and B intervals do not overlap)
- Duplicate intervals (A and B has exact start and end time)
Important Patterns and Techniques in Intervals Questions
Important patterns and techniques in intervals questions include understanding the basic operations of intervals, such as creating, merging, and querying, and using interval techniques in the design of algorithms, such as scheduling and range search.
The interval related questions have following patterns -
Note : A and B are time intervals
- A and B do not overlap
- A and B overlap but B ends after A
- A completely overlaps B
- A and B overlap but A ends after B
- B completely overlaps A
- A and B do not overlap
Most Important Questions with Solutions
Note : New Intervals questions with solutions are added every day. So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important Intervals questions.
Merge Intervals
Question —
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example :
Input:intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]Solution :
Main Logic/Idea —
The main logic is to sort the intervals by the start value and then traverse through the intervals list and compare the last meeting end time with new meeting start time. If found overlap then append the start and end interval in the result list and return the new list.
Implementation —
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda i:i[0])
ans = [intervals[0]]
for s,e in intervals[1:]:
lastMeeting = ans[-1][1]
if s<=lastMeeting:
ans[-1][1] = max(lastMeeting,e)
else:
ans.append([s,e])
return ansQuestion Link
Similar Pattern —
Amount of New Area Painted Each Day
Longest Substring of One Repeating Character
Divide Intervals Into Minimum Number of Groups
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Insert Interval
Question —
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Example :
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]Solution :
Main Logic/Idea —
Since the intervals list is already sorted by the start value, traverse through the intervals list and compare the end value of the new interval list with the start value of the sorted interval list. Append if the end value is less than the start value. You can calculate the new interval by taking min of start of both the interval list and max of end value of both the interval lists.
Implementation —
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
ans = []
for i in range(len(intervals)):
if newInterval[1] < intervals[i][0]:
ans.append(newInterval)
return ans+intervals[i:]
elif newInterval[0] > intervals[i][1]:
ans.append(intervals[i])
else:
newInterval = [min(newInterval[0],intervals[i][0]),
max(newInterval[1],intervals[i][1])]
ans.append(newInterval)
return ansQuestion Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New Intervals questions with solutions are added every day. So keep checking this post daily.
Tips and Techniques to solve Intervals Questions Fast.
Before solving interval question check if —
- Intervals are sorted or not.
- Intervals overlap or not.
- Merge overlapping intervals and form a new list with new intervals range.
- Intervals partially overlap and which interval ends/starts first.
- Learn how to insert intervals in between other intervals,
- To merge the intervals, merge the range of min of starting times and maximum of ending times.
That’s it for now. Day 23 : Bit Manipulation coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
