📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3001| 回复: 7
跳转到指定楼层
上一主题 下一主题
收起左侧

Google : Combine intervals

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
一个range的序列,如[1,3], [2,6], [8,10],[15,18]
: 写程序合并有重叠的range,比如上面的序列合并为[1,6], [8,10], [15,18]

上一篇:Google : Re-order data packets
下一篇:Google : 有关google地图实现的一个问题
🔗
 楼主| wwwyhx 2011-9-12 03:00:25 | 只看该作者
全局:
有种方法是:
1. 对所有端点排序(不分起始和结束端点)
2. 对排序的端点遍历, 并维护一个堆栈. 如果是起始节点就入栈, 碰到结束端点
就出栈, 如果出栈后为空,那么这个出栈的起始端点和碰到的结束端点就是一个大段

  1. struct END
  2. {
  3.         bool bStart;
  4.         int nVal;
  5. };

  6. bool LessThan(const END& ed1, const END& ed2)
  7. {
  8.         return ed1.nVal < ed2.nVal;
  9. }

  10. void PrintMerge(int a[], int n)
  11. {
  12.         assert(a && n%2 == 0 && n > 0);

  13.         END* pEnds = new END[n];
  14.         for (int i = 0; i < n; i++)
  15.         {
  16.                 pEnds[i].nVal = a[i];
  17.                 pEnds[i].bStart = (i%2 == 0);
  18.         }

  19.         sort(pEnds, pEnds + n, LessThan);

  20.         stack<END*> stk;
  21.         for (int i = 0; i < n; i++)
  22.         {
  23.                 if (pEnds[i].bStart)
  24.                         stk.push(&pEnds[i]);
  25.                 else
  26.                 {
  27.                         if (stk.empty()) break;

  28.                         END* p = stk.top();
  29.                         stk.pop();

  30.                         if (stk.empty())
  31.                                 cout<<p->nVal<<" "<<pEnds[i].nVal<<endl;
  32.                 }
  33.         }

  34.         delete []pEnds;
  35. }
复制代码
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-11-4 03:03:21 | 只看该作者
全局:
我觉得可以只对起点排序。
然后依次扫描。设当前合并段的起点为s, 终点为e。下一个要比较的段,起点为i,终点j:
if(i  e) e = j; //合并下一段,延长终点。
}else{
  //保存当前s,e,然后开始一个新的合并段
  i = s; e = j;
}
burself 发表于 2011-11-3 19:14


对啊, 这样简单多了, 谢了

  1. void PrintMerge2(int a[], int n)
  2. {
  3.         assert(a && n > 0 && n%2 == 0);

  4.         int nBeg = a[0];
  5.         int nEnd = a[1];

  6.         for (int i = 2; i < n; i += 2)
  7.         {
  8.                 if (a[i] > nEnd)
  9.                 {
  10.                         cout<<nBeg<<" "<<nEnd<<endl;
  11.                         nBeg = a[i];
  12.                         nEnd = a[i+1];
  13.                 }
  14.                 else
  15.                 {
  16.                         if (a[i+1] > nEnd)
  17.                                 nEnd = a[i+1];
  18.                 }
  19.         }

  20.         cout<<nBeg<<" "<<nEnd<<endl;
  21. }
复制代码
回复

使用道具 举报

🔗
ziegfeld 2011-11-4 04:46:32 | 只看该作者
全局:
我觉得可以只对起点排序。
然后依次扫描。设当前合并段的起点为s, 终点为e。下一个要比较的段,起点为i,终点j:
if(i  e) e = j; //合并下一段,延长终点。
}else{
  //保存当前s,e,然后开始一个新的合并段
  i = s; e = j;
}
burself 发表于 2011-11-3 19:14

+1
我还真这样做过。
项目里用到了。
回复

使用道具 举报

🔗
imwmwm 2011-11-6 02:21:13 | 只看该作者
全局:
算法书里讲贪心的时候提过这个interval scheduling的问题 反正就是要先按某种规则排序....
回复

使用道具 举报

🔗
imwmwm 2011-11-6 03:32:56 | 只看该作者
全局:
  1. public class CombineIntervals {

  2.         /**
  3.          * @param args
  4.          */
  5.         public static void main(String[] args) {
  6.                 // TODO Auto-generated method stub
  7.                 Pair[] p = {new Pair(2,3),
  8.                                         new Pair(1,4),
  9.                                         new Pair(5,7),
  10.                                         new Pair(6,9),
  11.                                         new Pair(3,4),
  12.                                         new Pair(1,2),
  13.                                         new Pair(8,11),
  14.                                         new Pair(12,13)};
  15.                 ArrayList<Pair> pairs = combineIntervals(p);
  16.                 System.out.println(pairs.toString());
  17.         }
  18.        
  19.         public static Pair combine(Pair p1, Pair p2){
  20.                 return new Pair(p1.beg, p1.end > p2.end ? p1.end : p2.end);
  21.         }
  22.        
  23.        
  24.         public static ArrayList<Pair> combineIntervals(Pair[] pairs){
  25.                 ArrayList<Pair> result = new ArrayList<Pair>();
  26.                 //sort pairs accordind to beg
  27.                 Arrays.sort(pairs, new PairComparator());

  28.                 int currentEnd = pairs[0].end;
  29.                 int currentIndex = 0;
  30.                 result.add(pairs[0]);
  31.                 for(int i = 1; i < pairs.length; i++){
  32.                         if(pairs[i].beg <= currentEnd){
  33.                                 Pair p = combine(result.get(currentIndex), pairs[i]);
  34.                                 result.remove(currentIndex);
  35.                                 result.add(p);
  36.                                 currentEnd = p.end;
  37.                         }else{
  38.                                 result.add(pairs[i]);
  39.                                 currentEnd = pairs[i].end;
  40.                                 currentIndex++;
  41.                         }
  42.                 }
  43.                 return result;

  44.         }
  45. }
复制代码


来个完整的...
回复

使用道具 举报

🔗
alex_901 2011-11-16 04:51:33 | 只看该作者
全局:
  1. class DataSet {
  2.         public int begin;
  3.         public int end;

  4.         public DataSet(int i, int j) {
  5.                 begin = i;
  6.                 end = j;
  7.         }
  8. }

  9. class StackX {
  10.         private int top;     
  11.         private int[] stackArray;
  12.         private int size;

  13.         public StackX(int i) {
  14.                 top = -1;
  15.                 size = i;
  16.                 stackArray = new int[size];
  17.         }

  18.         public void push(int i) {
  19.                 stackArray[++top] = i;
  20.         }

  21.         public int peek() {
  22.                 return stackArray[top];
  23.         }

  24.         public int pop() {
  25.                 int temp = stackArray[top--];
  26.                 return temp;
  27.         }
  28.        
  29.         public boolean isEmpty() {
  30.                 return top == -1;
  31.         }
  32. }

  33. class DSArray {
  34.         private DataSet[] DSArr;
  35.         private int num;
  36.         private final int MAX_NUM = 10;
  37.         private int[] elementArr;
  38.         private StackX stackImpl;
  39.         private DataSet[] newDS;
  40.         private int k = 0;

  41.         public DSArray() {
  42.                 DSArr = new DataSet[MAX_NUM];
  43.                 elementArr = new int[MAX_NUM * 2];
  44.                 num = 0;
  45.                 stackImpl = new StackX(MAX_NUM);
  46.         }
  47.        
  48.         public void combine() {
  49.                 newDS = new DataSet[MAX_NUM];
  50.                
  51.                 for (int i = 0; i < num * 2; i++) {
  52.                         if (isBegin(elementArr[i])) {
  53.                                 stackImpl.push(elementArr[i]);

  54.                                 //System.out.println("The element pushed is: " + elementArr[i]);
  55.                         } else {
  56.                                 int temp = stackImpl.pop();

  57.                                 if (stackImpl.isEmpty()) {

  58.                                         //System.out.println("The current number of new data sets is: " + k);
  59.                                         DataSet ds = new DataSet(temp, elementArr[i]);
  60.                                         //System.out.print("[" + ds.begin + ", " + ds.end + "]");
  61.                                         newDS[k++] = ds;
  62.                                 }
  63.                         }
  64.                 }
  65.         }

  66.         public void displayNewDS() {
  67.                 System.out.println("All the new data sets are: ");

  68.                 //System.out.println("The size of newDS[] is: " + newDS.length);

  69.                 for (int i = 0; i < k; i++) {
  70.                         System.out.print("[" + newDS[i].begin + ", " + newDS[i].end + "]");
  71.                 }

  72.                 System.out.println();
  73.         }

  74.         public boolean isBegin(int i) {
  75.                 for (int j = 0; j < num; j++) {
  76.                         if (i == DSArr[j].begin) {
  77.                                 return true;
  78.                         }
  79.                 }

  80.                 return false;
  81.         }

  82.         public void insert(int b, int e) {
  83.                 DataSet ds = new DataSet(b, e);
  84.                 DSArr[num++] = ds;
  85.         }

  86.         public void move() {
  87.                 int j = 0;

  88.                 for (int k = 0; k < num; k++) {
  89.                         elementArr[j] = DSArr[k].begin;
  90.                         j++;
  91.                         elementArr[j] = DSArr[k].end;
  92.                         j++;
  93.                 }
  94.         }

  95.         public void displayDataSets() {
  96.                 System.out.println("All the data sets are: ");

  97.                 for (int i = 0; i < num; i++) {
  98.                         System.out.print("[" + DSArr[i].begin + ", " + DSArr[i].end + "]");
  99.                         System.out.print(" ");
  100.                 }
  101.                
  102.                 System.out.println();
  103.         }

  104.         public void displayElements() {
  105.                 System.out.println("All the elements in datasets are: ");

  106.                 for (int a = 0; a < num * 2; a++) {
  107.                         System.out.print(elementArr[a] + " ");
  108.                 }

  109.                 System.out.println();
  110.         }

  111.         public void quickSort(int left, int right) {
  112.                 if (left >= right) {
  113.                         return;
  114.                 } else {
  115.                         int pivot = elementArr[right];
  116.                         int p = partition(left, right, pivot);
  117.                         quickSort(left, p - 1);
  118.                         quickSort(p + 1, right);
  119.                 }
  120.         }

  121.         public int partition(int left, int right, int pivot) {
  122.                 int lptr = left - 1;
  123.                 int rptr = right;
  124.         while (true) {
  125.                 while (elementArr[++lptr] < pivot) {
  126.                         ;
  127.                 }

  128.                 while (rptr > 0 && elementArr[--rptr] > pivot) {
  129.                         ;
  130.                 }

  131.                 if (lptr >= rptr) {
  132.                         break;
  133.                 } else {
  134.                         swap(lptr, rptr);
  135.                 }
  136.         }
  137.                 swap(lptr, right);
  138.                 return lptr;
  139.         }

  140.         public void swap(int l, int r) {
  141.                 int temp;
  142.                 temp = elementArr[l];
  143.                 elementArr[l] = elementArr[r];
  144.                 elementArr[r] = temp;
  145.         }
  146. }

  147. public class CombineIntervals {
  148.         public static void main(String[] args) {
  149.                
  150.                 int DataSetsNUM = 4;               

  151.                 DSArray dsa = new DSArray();
  152.                 dsa.insert(2, 4);
  153.                 dsa.insert(3, 7);
  154.                 dsa.insert(1, 7);
  155.                 dsa.insert(10, 18);
  156.                
  157.                 dsa.displayDataSets();
  158.                 dsa.move();
  159.                 dsa.quickSort(0, DataSetsNUM * 2 - 1);

  160.                 dsa.displayElements();
  161.                 dsa.combine();
  162.                 dsa.displayNewDS();
  163.         }
  164. }
复制代码


来个超完整版
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表