بالنظر إلى فترات عديدة مثل النطاقات وموقعنا. نحن بحاجة إلى إيجاد الحد الأدنى من المسافة للسفر للوصول إلى هذه النقطة التي تغطي جميع الفواصل الزمنية في وقت واحد.
أمثلة:
Input : Intervals = [(0 7) (2 14) (4 6)] Position = 3 Output : 1 We can reach position 4 by travelling distance 1 at which all intervals will be covered. So answer will be 1 Input : Intervals = [(1 2) (2 3) (3 4)] Position = 2 Output : -1 It is not possible to cover all intervals at once at any point Input : Intervals = [(1 2) (2 3) (1 4)] Position = 2 Output : 0 All Intervals are covered at current position only so no need travel and answer will be 0 All above examples are shown in below diagram.
يمكننا حل هذه المشكلة من خلال التركيز فقط على نقاط النهاية. نظرًا لأن الشرط هو تغطية جميع الفواصل الزمنية من خلال الوصول إلى نقطة ما، يجب أن تشترك جميع الفواصل الزمنية في نقطة واحدة حتى تكون الإجابة موجودة. حتى الفاصل الزمني الذي يقع في أقصى اليسار يجب أن يتداخل مع الفاصل الزمني في أقصى نقطة البداية.
أولاً نجد نقطة البداية اليمنى ونقطة النهاية اليسرى من جميع الفواصل الزمنية. ومن ثم يمكننا مقارنة موقفنا مع هذه النقاط للحصول على النتيجة الموضحة أدناه:
- إذا كانت نقطة البداية اليمنى هذه تقع على يمين نقطة النهاية اليسرى، فمن غير الممكن تغطية جميع الفواصل الزمنية في وقت واحد. (كما في المثال 2)
- إذا كان موقعنا في المنتصف بين اليمين عند أقصى البداية واليسار عند أقصى النهاية، فلن تكون هناك حاجة للسفر وسيتم تغطية جميع الفواصل الزمنية بالموقع الحالي فقط (كما في المثال 3)
- إذا ترك موقعنا عند كلا النقطتين، فسنحتاج إلى الانتقال إلى نقطة البداية في أقصى اليمين، وإذا كان موقعنا على حق في كلتا النقطتين، فعلينا السفر إلى نقطة النهاية في أقصى اليسار.
الرجوع إلى الرسم البياني أعلاه لفهم هذه الحالات. كما هو الحال في المثال الأول، فإن معظم البداية اليمنى هي 4 ومعظم النهاية اليسرى هي 6، لذا نحتاج إلى الوصول إلى 4 من الموضع الحالي 3 لتغطية جميع الفواصل الزمنية.
يرجى الاطلاع على الكود أدناه لفهم أفضل.
C++// C++ program to find minimum distance to // travel to cover all intervals #include
// Java program to find minimum distance // to travel to cover all intervals import java.util.*; class GFG{ // Structure to store an interval static class Interval { int start end; Interval(int start int end) { this.start = start; this.end = end; } }; // Method returns minimum distance to // travel to cover all intervals static int minDistanceToCoverIntervals(Interval intervals[] int N int x) { int rightMostStart = Integer.MIN_VALUE; int leftMostEnd = Integer.MAX_VALUE; // Looping over all intervals to get // right most start and left most end for(int i = 0; i < N; i++) { if (rightMostStart < intervals[i].start) rightMostStart = intervals[i].start; if (leftMostEnd > intervals[i].end) leftMostEnd = intervals[i].end; } int res; // If rightmost start > leftmost end then // all intervals are not aligned and it // is not possible to cover all of them if (rightMostStart > leftMostEnd) res = -1; // If x is in between rightmoststart and // leftmostend then no need to travel // any distance else if (rightMostStart <= x && x <= leftMostEnd) res = 0; // Choose minimum according to // current position x else res = (x < rightMostStart) ? (rightMostStart - x) : (x - leftMostEnd); return res; } // Driver code public static void main(String[] args) { int x = 3; Interval []intervals = { new Interval(0 7) new Interval(2 14) new Interval(4 6) }; int N = intervals.length; int res = minDistanceToCoverIntervals( intervals N x); if (res == -1) System.out.print('Not Possible to ' + 'cover all intervalsn'); else System.out.print(res + 'n'); } } // This code is contributed by Rajput-Ji
# Python program to find minimum distance to # travel to cover all intervals # Method returns minimum distance to travel # to cover all intervals def minDistanceToCoverIntervals(Intervals N x): rightMostStart = Intervals[0][0] leftMostStart = Intervals[0][1] # looping over all intervals to get right most # start and left most end for curr in Intervals: if rightMostStart < curr[0]: rightMostStart = curr[0] if leftMostStart > curr[1]: leftMostStart = curr[1] # if rightmost start > leftmost end then all # intervals are not aligned and it is not # possible to cover all of them if rightMostStart > leftMostStart: res = -1 # if x is in between rightmoststart and # leftmostend then no need to travel any distance else if rightMostStart <= x and x <= leftMostStart: res = 0 # choose minimum according to current position x else: res = rightMostStart-x if x < rightMostStart else x-leftMostStart return res # Driver code to test above methods Intervals = [[0 7] [2 14] [4 6]] N = len(Intervals) x = 3 res = minDistanceToCoverIntervals(Intervals N x) if res == -1: print('Not Possible to cover all intervals') else: print(res) # This code is contributed by rj13to.
// C# program to find minimum distance // to travel to cover all intervals using System; class GFG{ // Structure to store an interval public class Interval { public int start end; public Interval(int start int end) { this.start = start; this.end = end; } }; // Method returns minimum distance to // travel to cover all intervals static int minDistanceToCoverIntervals( Interval []intervals int N int x) { int rightMostStart = int.MinValue; int leftMostEnd = int.MaxValue; // Looping over all intervals to get // right most start and left most end for(int i = 0; i < N; i++) { if (rightMostStart < intervals[i].start) rightMostStart = intervals[i].start; if (leftMostEnd > intervals[i].end) leftMostEnd = intervals[i].end; } int res; // If rightmost start > leftmost end then // all intervals are not aligned and it // is not possible to cover all of them if (rightMostStart > leftMostEnd) res = -1; // If x is in between rightmoststart and // leftmostend then no need to travel // any distance else if (rightMostStart <= x && x <= leftMostEnd) res = 0; // Choose minimum according to // current position x else res = (x < rightMostStart) ? (rightMostStart - x) : (x - leftMostEnd); return res; } // Driver code public static void Main(String[] args) { int x = 3; Interval []intervals = { new Interval(0 7) new Interval(2 14) new Interval(4 6) }; int N = intervals.Length; int res = minDistanceToCoverIntervals( intervals N x); if (res == -1) Console.Write('Not Possible to ' + 'cover all intervalsn'); else Console.Write(res + 'n'); } } // This code is contributed by shikhasingrajput
<script> // JavaScript program to find minimum distance to // travel to cover all intervals // Method returns minimum distance to travel // to cover all intervals function minDistanceToCoverIntervals(Intervals N x){ let rightMostStart = Intervals[0][0] let leftMostStart = Intervals[0][1] // looping over all intervals to get right most // start and left most end for(let curr of Intervals){ if(rightMostStart < curr[0]) rightMostStart = curr[0] if(leftMostStart > curr[1]) leftMostStart = curr[1] } let res; // if rightmost start > leftmost end then all // intervals are not aligned and it is not // possible to cover all of them if(rightMostStart > leftMostStart) res = -1 // if x is in between rightmoststart and // leftmostend then no need to travel any distance else if(rightMostStart <= x && x <= leftMostStart) res = 0 // choose minimum according to current position x else res = (x < rightMostStart)?rightMostStart-x : x-leftMostStart return res } // Driver code to test above methods let Intervals = [[0 7] [2 14] [4 6]] let N = Intervals.length let x = 3 let res = minDistanceToCoverIntervals(Intervals N x) if(res == -1) document.write('Not Possible to cover all intervals''
') else document.write(res) // This code is contributed by shinjanpatra </script>
الإخراج:
1
تعقيد الوقت: على)
المساحة المساعدة: على)